Question

Suppose you are given two circularly linked lists, L and M. Create an algorithm
for telling if L and M store the same sequence of elements (but perhaps with
different starting points). Please provide a main() function with it in Java to test it.

Answer 1

public class Test {
   public static void main(String[] args){
       CircularLinkedList list1 = new CircularLinkedList();
       list1.append(6);
       list1.append(2);
       list1.append(3);
       list1.append(4);
       list1.append(5);
      
       CircularLinkedList list2 = new CircularLinkedList();
       list2.append(2);
       list2.append(3);
       list2.append(4);
       list2.append(5);
       list2.append(6);
      
       list1.displayList();
       list2.displayList();
      
       System.out.println(" check :"+checkSame(list1,list2));
      
       list1.append(3);
       list2.append(10);
       list1.displayList();
       list2.displayList();
       System.out.println(" check :"+checkSame(list1,list2));
      
      
      
   }
  
   public static boolean checkSame(CircularLinkedList l1,CircularLinkedList l2){
       if(l1.getCount() != l2.getCount()) return false;
       else{
           Node l1_start = l1.getStartNode();
           Node l2_start = l2.getStartNode();
           Node n1=l1.getStartNode();
           Node n2=l2.getStartNode();
           while(n2.link != l2_start){
               if(n2.data==n1.data){
                   break;
               }
               n2=n2.link;
           }
           while(n1.link != l1_start){
               if(n1.data != n2.data){
                   return false;
               }
               n1=n1.link;
               n2=n2.link;
           }
           return true;
       }
   }
}
class Node{
    int data;
    public Node link;
    public Node(int data){
        this.data=data;
    }
    @SuppressWarnings("unused")
    public Node(int data,Node link){
        this.data=data;
        this.link=link;
    }
   }
class CircularLinkedList {
    private Node start;
    private int count;
    public void append(int x){
        count++;
        Node temp=new Node(x);
        if(start==null){
            start=temp;
        }else{
            Node tp=start;
            while(tp.link!=start){
                tp=tp.link;
            }
            tp.link=temp;
        }
        temp.link=start;
    }
    public void addBeg(int x){
        count++;
        Node temp=new Node(x);
        if(start==null){
            temp.link=temp;
        }else{
            Node tp=start;
            while(tp.link!=start){
                tp=tp.link;
            }
            tp.link=temp;
            temp.link=start;
        }
        start=temp;
    }
    public void addAt(int pos,int x){
        Node temp,tp;
        temp=new Node(x);
        tp=start;
        for(int i=0;i<pos;i++){
            if(tp.link==start)
                break;
            tp=tp.link;
        }
        temp.link=tp.link;
        tp.link=temp;
        count++;
    }
    public void displayList(){
        if(start==null)
            System.out.println("List is empty..");
        else{
        Node temp=start;
        System.out.print("[ ");
        while(temp.link!=start){
            System.out.print(" "+temp.data+" ");
            temp=temp.link;
        }
        System.out.print(temp.data+" ]");
        System.out.println();
    }
}
    public void deleteAt(int position){
        Node current=start;
        Node previous=start;
        for(int i=0;i<position;i++){
            if(current.link==start)
                break;
            previous=current;
            current=current.link;
        }
        System.out.print(current.data);
        if(position==0)
            deleteFirst();
        else
            previous.link=current.link;
        count--;
    }
    public Node getStartNode(){
       return start;
    }
    public void deleteFirst() {
        Node temp=start;
        while(temp.link!=start){
            temp=temp.link;
        }
        temp.link=start.link;
        start=start.link;
        count--;
    }
    public int getCount(){
        return count;
    }
}