Untitled

 CAT -1
1) LOOP DETECTION
import java.util.*;
class Node{
        int data;
        Node next;
         Node(int e)
        {
            data=e;
            next=null;
        }
    }
public class Main{
    
    static Node head=null,temp=null;
    static int count=1;
public static void insert(int e)
        {
            temp =new Node(e);
            if(head==null)
            head=temp;
 else{
                Node cur=head;
                while(cur.next!=null)
                    cur=cur.next;
                 cur.next=temp;
            }
        }
public static void create(int k)
        {
            Node t=head;
            while(count<k)
            {
                t=t.next;
                count++;
            }
            temp.next=t;
        }
public static  void cycleDetect()
    {
        Node fast = head;
        Node slow = head;
         

while (fast.next != null && fast.next.next != null) 
        {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                System.out.println("Loop found");
                return;
            }
        }
        System.out.println("No Loop");
    }
 public static void print()
    {
        Node t=head;
        while(t!=null)
    {
        System.out.print(t.data);
        t=t.next;
    }
    }
    
    
 public static void main(String[] args)
    {
      Scanner sc=new Scanner(System.in);
      int e,k;
      
      while(true)
      {
          e=sc.nextInt();
          if(e<0)
             break;
        insert(e);
      }
	print();
      k=sc.nextInt();
      create(k);
      cycleDetect();
     
    }
}

2)SEGREGATE EVEN AFTER ODD 
import java.io.*;
import java.util.*;

public class Solution {
    Node head;
    class Node
    {
        int data;
        Node next;
        Node(int val)
        {
            data = val;
            next = null;
        }
    }
    public void insert(int val)
    {
        Node newnode = new Node(val);
        Node temp = head;
        if(head == null)
            head = newnode;
        else
        {
        while(temp.next!=null)
        {
            temp = temp.next;
        }
        temp.next = newnode;
    }
    }
    public void segOddEven()
    {
        Node evenstart = null;
        Node evenend = null;
        Node oddstart = null;
        Node oddend = null;
        Node currentnode = head;
        while(currentnode!=null)
        {
            int element = currentnode.data;
            if(element%2==0)
            {
                if(evenstart==null)
                {
                    evenstart = currentnode;
                    evenend = evenstart;
                }
                else
                {
                    evenend.next = currentnode;
                    evenend = evenend.next;
                }
            }
            else
            {
                if(oddstart == null)
                {
                    oddstart = currentnode;
                    oddend = oddstart;
                }
                else
                {
                    oddend.next = currentnode;
                    oddend = oddend.next;
                } 
            }
            currentnode = currentnode.next;
        }
         if (oddstart == null) {
        head = evenstart;
    } else {
        head = oddstart;
        oddend.next = evenstart;
    }

    // Set the next of the last node of the even list to null
    if (evenend != null) {
        evenend.next = null;
    }
}
    public void display()
    {
        Node temp = head;
        while(temp!=null)
        {
            System.out.print(temp.data+" ");
            temp = temp.next;
        }
    }
    public static void main(String[] args) {
    Solution list = new Solution();
        Scanner s = new Scanner(System.in);
        int x = s.nextInt();//1
        while(x!=-1)
        {
            list.insert(x);//1
            x = s.nextInt();//2
        }
        list.segOddEven();
        list.display();
    }
}

3) BITONIC SORT USING DLL
import java.util.*;
class node
{
    int data;
    node prev;
    node next;
}
class solution
{
    static node head=null,temp=null;
    public static void insert(int data)
    {
        node newnode=new node();
        newnode.data=data;
        newnode.next=null;
        newnode.prev=null;
        if (head==null)
        {
            head=newnode;
            temp=newnode;
            temp.prev=null;
        }
        else
        {
            temp.next=newnode;
           newnode.prev=temp;
            temp=newnode;
        }
    }
    public static void display()
    {
        while(head!=null)
        {
            System.out.print(head.data+" ");
            head=head.next;
        }
    }
    public static void bitonic()
    {
        node i=head,j=temp,t=null;
        while(i!=j)
        {
            if(i.data>j.data)
            {
                j.prev.next=null;
                t=j.prev;
                j.prev=null;
                if(i.prev==null)
                {
                    head=j;
                    j.next=i;
                    i.prev=j;
                }
                else
                {
                    j.prev=i.prev;
                    i.prev.next=j;
                    j.next=i;
                    i.prev=j;
                    
                }
                j=t;
            }
            i=i.next;
        }
    }
    public static void main(String []args)
    {
        Scanner in=new Scanner(System.in);
        while(true)
        {
            int n=in.nextInt();
            if(n<0)
            {
                break;
            }
            else
            {
                insert(n);
            }
        }
        bitonic();
        display();
    }
    
}

4)MINIMUM STACK
import java.util.*;
class Mystack {
	Stack<Integer> s;
	Stack<Integer> a;
	Mystack() {
		s = new Stack<Integer>();
		a = new Stack<Integer>();
	}
	void getMin() {
		if(a.isEmpty())
			System.out.println(“Stack is Empty”);
		else
			System.out.println(“Minimum element : “ + a.peek());
	}

void peek(){	
	if(s.isEmpty()) {
		System.out.println(“Stack is Empty”);
		return ;
	}
	integer t=s.peek();
	System.out.print(“Top most element:” + t);
}
void pop() {
	if(s.isEmpty()) {
		System.out.println(“Stack is Empty”);
		return ;}
	else{
	int t = s.pop();
	System.out.println(“Removed element : “ + t);} 

	
	if( t == a.peek() )
		a.pop();
}
void push(int x) {
	if ( s.isEmpty()) {
		s.push(x);
		a.push(x)
		System.out.println(“ Number Inserted: “+ x);
		return ;
	}
	else {
		s.push(x);
		System.out.prinln(“ Number Inserted: “ +x);
	}
	if ( x<= a.peek() ) 
		a.push(x);
	}
};
public class Main {
	public static void main(String args[]) {
		Mystack s=new Mystack();
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		for( int i=0;i<n;i++) {
			int m=sc.nextInt();
			s.push(m);
		} 
	s.getMin();
	s.pop();
	s.getMin();
	s.pop();
	s.peek();
	}
}
5)THE CELEBRITY PROBLEM
 import java.util.*;
public class CP
{
    Stack<Integer> s=new Stack<Integer>();
    int cpp(int ar[][],int n){
        for(int i=0;i<n;i++){
            s.push(i);
        }
        
        while(s.size()>1){
            int a=s.pop();
            int b=s.pop();
            if(ar[a][b]==1){
                s.push(b);
            }
            else{
                s.push(a);
            }
        }
        int a=s.pop();
        for(int i=0;i<n;i++){
            if(a==i){
                continue;
            }
            else{
                if(ar[i][a]==0 || ar[a][i]==1){
                    return -1;
                }
            }
            
        }
        return a;
    }
    
        
	public static void main(String[] args) {
		CP s=new CP();
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int ar[][]=new int[n][n];
		for(int i=0;i<n;i++){
		    for(int j=0;j<n;j++){
		        ar[i][j]=in.nextInt();
		    }
		}
		 System.out.print(s.cpp(ar,n));
	}	
		
}
6) TOWER OF HANOI
import java.util.*;
class Main{
   static Stack <Integer> sor=new Stack<Integer>();
     static Stack <Integer> aux=new Stack<Integer>();
      static Stack <Integer> des=new Stack<Integer>();
      void change( Stack <Integer> disk1, Stack <Integer> disk2, char p1, char p2)
      {
          int v1,v2;
          if(disk1.isEmpty())
            v1=Integer.MIN_VALUE;
        else
            v1=disk1.pop();
        if(disk2.isEmpty())
            v2=Integer.MIN_VALUE;
        else
            v2=disk2.pop();
            
            
     if(v1==Integer.MIN_VALUE)
     {
         disk1.push(v2);
         System.out.println("The value"+v2+" move from "+p2+" to "+p1);
     }
     else if(v2==Integer.MIN_VALUE){
         disk2.push(v1);
         System.out.println("The value"+v1+" move from "+p1+" to "+p2);
     }
     else if(v1<v2)
     {
        disk2.push(v1);
         disk2.push(v1);
         System.out.println("The value"+v1+" move from "+p1+" to "+p2);
     }
     else
     {
         disk1.push(v1);
         disk1.push(v2);
         System.out.println("The value"+v2+" move from "+p2+" to "+p1);
     }
      }
    
    public static void main(String [] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        Main ob=new Main();
        char s='S',d='D',a='A';
        
        if(n%2==0)
        {
            char temp=a;
            a=d;
            d=temp;
        }
        int moves=(int)(Math.pow(2,n))-1;
        for(int i=n;i>0;i--)
        {
           ob. sor.push(i);
            
        }
         for(int i=1;i<=moves;i++)
         {
             if(i%3==1)
                 ob.change(sor,des,s,d);
             else if(i%3==2)
                 ob.change(sor, aux,s,a);
            else if(i%3==0)
           ob.change(aux,des,a,d);
        }}}


7) MAXIMUM SLIDING WINDOW
import java.util.*;
public class Main
{
    public static int[] maxs(int[] arr, int n, int k)
    {
        int [] ans=new int[n-k+1];
        Deque<Integer> q=new ArrayDeque<>();
        for(int i=0;i<k;i++)
        {
            while(!q.isEmpty()&& arr[i]>=arr[q.peekLast()])
                q.removeLast();
            q.addLast(i);
        }
        ans[0]=arr[q.peekFirst()];
        for(int i=k;i<n;i++)
        {
            while(!q.isEmpty()&&q.peekFirst()<=i-k)
                q.pollFirst();
            while(!q.isEmpty() && arr[i]>=arr[q.peekLast()])
                q.pollLast();
            q.addLast(i);
        ans[i-k+1]=arr[q.peekFirst()];
        }
        return ans;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int arr[]=new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i]=sc.nextInt();
        }
        int k=sc.nextInt();
        int[]ans=maxs(arr,n,k);
        for(int i:ans)
          System.out.print(i+" ");
        
    }
}
8) STACK PERMUTATIONS
import java.util.*;
public class Main {	
public static Boolean checkPermutation(int a[],int b[],int n)	
{		
    Queue<Integer> input = new LinkedList<>();		
    for(int i=0;i<n;i++)	
         input.add(a[i]);
     Queue<Integer> output = new LinkedList<>();		
    for(int i=0;i<n;i++)	
          output.add(b[i]); 	
    Stack<Integer> stack = new Stack<>();		
    int j=0;		
    for(int i=0;i<n;i++){			
       stack.push(input.peek());			
       while(stack.size()>0 && stack.peek()== output.peek())
{	 
                 stack.pop();				
                 output.poll();				
                 j++;			
       }			
       input.poll(); 	
    }		
    if(j==n && stack.size()==0)	
        return true;		
    else			
       return false;	
}
public static void main(String[] args){	
    Scanner s = new Scanner(System.in);	
    int n = s.nextInt();	
    int a[] = new int[n];	
    for(int i =0;i<n;i++)	
{		
            a[i] = s.nextInt();	
}	
    int b[] = new int[n];	
    for(int i=0;i<n;i++)	
{		
             b[i] = s.nextInt();	
}	
    if(checkPermutation(a,b,n)== true)		
       System.out.print("Yes");	
    else		 
     System.out.println("Not possible");
}
}
 

9) PRIORITY QUEUE USING DLL
import java.util.*;
class node
{
    int data,prio;
    node prev,next;
}
class Main 
{
    node front=null,rear=null;
    void insert(int data,int prio)
    {
        node newnode=new node();
        newnode.data=data;
         newnode.prio=prio;
         newnode.prev=null;
         newnode.next=null;
         if(front==null)
         {
             front=newnode;
             rear=newnode;
         }
         else
         {
            if(prio<=front.prio)
            {
                newnode.next=front;
                front.prev=newnode;
                front=newnode;
            }
            else if(prio>=rear.prio)
            {
                rear.next=newnode;
                newnode.prev=rear;
                rear=newnode;
            }
            else{
                while(front!=null&&front.next.prio<=prio)
                {
                    front=front.next;
                }
                newnode.prev=front;
                newnode.next=front.next;
                front.next.prev=newnode;
                front.next=newnode;
                
            }
         }
    }
    void print()
    {
        while(front!=null)
        {
            System.out.print(front.data+" "+front.prio+" ");
            front=front.next;
        }
    }
    public static void main(String[]args)
    {
        Scanner in=new Scanner(System.in);
        Main obj=new Main();
        int n=in.nextInt();
        for(int i=0;i<n;i++)
        {
            int data=in.nextInt();
            int priority=in.nextInt();
            obj.insert(data,priority);
        }
        obj.print();
    }
}

10) MEGE SORT USING DLL

import java.util.Scanner;
class Node {
    int data;
    Node next, prev;
    Node(int val){
        data = val;
        next = null;
        prev = null;
    }
}
class Main {
    public Node split(Node head) {
        Node fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        Node temp = slow.next;
        slow.next = null;
        return temp;
    }
    public Node mergeSort(Node node) {
        if (node == null || node.next == null)
            return node;
        Node second = split(node);
        node = mergeSort(node);
        second = mergeSort(second);
        return merge(node, second);
    }
    public Node merge(Node first, Node second) {
        if (first == null)
            return second;
        if (second == null)
            return first;
        if (first.data < second.data) {
            first.next = merge(first.next, second);
            first.next.prev = first;
            first.prev = null;
            return first;
        }
else {
    second.next = merge(first, second.next); 
    second.next.prev = second; 
    second.prev = null;
    return second;
}
    }
}
public class Solution
{
    public static void printList_left_right(Node head){
        while(head != null){
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.println();
    }
public static void printList_right_left(Node head){
        Node tail = head;
        while(tail.next != null)
            tail = tail.next;
        while(tail != null){
            System.out.print(tail.data + " ");
            tail = tail.prev;
        }
         System.out.println();
    }
public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int val = sc.nextInt();
        Node head = new Node(val);
        for(int i=0;i<n-1;i++){
            val = sc.nextInt();
            Node nd = new Node(val);
            nd.next = head;
            head = nd;
        }
        Main g = new Main();
        Node res = g.mergeSort(head);
        printList_left_right(res);
        printList_right_left(res);
    }
 

11) SORT WITHOUT EXTRA SPACE
import java.util.*;
class Main
{ 
	public static int minIndex(Queue<Integer> list, int sortIndex) 
	{ 
	int min_index = -1; 
	int min_value = Integer.MAX_VALUE; 
	int s = list.size(); 
	for (int i = 0; i < s; i++) 
	{ 
		int current = list.peek(); 
		list.poll(); 
		if (current <= min_value && i <= sortIndex) 
		{ 
			min_index = i; 
			min_value = current; 
		} 
		list.add(current); 
	} 
	return min_index; 
} 
public static void insertMinToRear(Queue<Integer> list, int min_index) { 
		int min_value = 0; 
		int s = list.size(); 
		for (int i = 0; i < s; i++) 
		{ 
		int current = list.peek(); 
		list.poll(); 
		if (i != min_index) 
			list.add(current); 
		else
			min_value = current; 
		} 
		list.add(min_value); 
	} 
	public static void sortQueue(Queue<Integer> list) { 
		for(int i = 1; i <= list.size(); i++) 
		{ 
			int min_index = minIndex(list,list.size() - i); 
			insertMinToRear(list, min_index); 
		} 
	} 
	public static void main (String[] args) 
	{ 
		Queue<Integer> list = new LinkedList<Integer>(); 
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		for(int i=0;i<n;i++)
		{
		   int ele=sc.nextInt();
		list.add(ele);
		}
		sortQueue(list); 
		while(list.isEmpty()== false) 
		{ 
			System.out.print(list.peek() + " "); 
			list.poll(); 
		} 
	} 
}

12) STOCKSPAN PROBLEM

import java.util.*;
class Main
{
Stack<Integer>s=new Stack<Integer>();
public static void main(String[]args)
{
Scanner in=new  Scanner(System.in);
int n=in.nextInt();
int []stock=new int[n];
for(int i=0;i<n;i++)
{
stock[i]=in.nextInt();
}
int[]span=new int[n];
for(int i=0;i<n;i++)
{
while(!s.isEmpty()&& stock[i]>=stock[s.peek()])
{
  s.pop();
}
if(s.isEmpty())
{
span[i]=1;
}
else
{
span[i]=i-s.peek();
}
s.push(i);
}
for(int i=0;i<n;i++)
{
System.out.print(span[i]+" ");
}
}
}