Detect And Remove Loop from LinkList


import java.util.HashSet;

class LinkList3{

    Node head;

    Node sl;
    Node ft;
    class Node{
        int data;
        Node next;
        public Node(int data,boolean flag, Node node){
            this.data=data;
            this.next=null;
        }

        @Override
        public String toString() {
            return "{"+this.data+"}";
        }
    }

    public Node push(int data,boolean flag, Node node){
        Node link=new Node(data,flag,node);
        if(head==null){
            head=link;
        }else{
            Node current=head;
            while(current.next!=null){
                current=current.next;
            }

            if(flag && node!=null){
                link.next=node;
            }
            current.next=link;
        }


        return link;
    }
    public void display(){
        Node current=head;
        while(current!=null){
            System.out.print(current);
            current=current.next;
        }

    }
    public boolean detectLoop1(){

        HashSet set=new HashSet();
        Node current=head;
        boolean flag=false;
        while(current.next!=null){
            if(set.contains(current)){
                flag=true;
               break;
            }
            set.add(current);
            current=current.next;
        }
        return flag;
    }

    public boolean detectLoop2(){
        sl=head;
        ft=head.next;

       while(sl!=ft){
            if(ft==null || ft.next==null){
                return false;
            }
            sl=sl.next;
            ft=ft.next.next;
       }
        return true;
    }

    public boolean removeLoop1(){

        HashSet set=new HashSet();
        Node previous=head;
        Node current=head;
        while(current!=null){
            if(set.contains(current)){
                previous.next=null;
                return true;
            }
            set.add(current);
            previous=current;
            current=current.next;
        }

        return false;

    }
    public void removeLoop2(){
       ft=head;
        while(ft!=null){
            Node ptr=sl;
            while(ptr.next!=sl && ptr.next!=ft){
                ptr=ptr.next;
            }
            if(ptr.next==ft){
                ptr.next=null;
                return;
            }
            ft=ft.next;
        }

    }
}

public class DetectLoop2 {
    public static void main(String[] args) {
        LinkList3 linkList3=new LinkList3();
        linkList3.push(10,false,null);
        LinkList3.Node push = linkList3.push(20, false, null);
        linkList3.push(30,false,null);
        linkList3.push(40,false,null);
        linkList3.push(50,true,push);
        boolean flag=false;
        //linkList3.display();
       // flag= linkList3.detectLoop1();
        flag= linkList3.detectLoop2();
        if(flag){
            System.out.println("loop found");
        }else{
            System.out.println("loop not found");
        }
        //linkList3.removeLoop1();
        linkList3.removeLoop2();
        linkList3.display();
    }
}


No comments:

Post a Comment