Question

Implement a function that detects if there is a “loop” in a singly linked list. A “loop” is defined as a link from one node to itself or to another node that is before the node in the list. The function may only make one pass through the list. It must return 1 if a “loop” exists; 0 otherwise. Be sure to test your function! You may start with code that you have written for other labs. This is a common interview question!

Answer 1

import java.util.*;

//class node
class Node{
   public Node next;
   public int data;
   Node(int d,Node n )
   {
       data=d;
       next=n;
   }
}

// class linked list
class LinkedListImplementation{
  
public Node head;
   LinkedListImplementation()
   {
       head=null;
   }
  
   // function that insert the node
   public void Insert(int e)
   {
       Node newNode=new Node(e,null);
       if(head==null)
       {
           head=newNode;
       }
      
       else if(head.next==null) {
           head.next=newNode;
       }
       else
       {
           Node temp=head;
           while(temp.next!=null)
           {
               temp=temp.next;
           }
           temp.next=newNode;
       }
   }
  
  
   //display the list
   public void displayList() {
       Node temp=head;
       while(temp!=null) {
           System.out.print(temp.data+"->");
           temp=temp.next;
       }
       System.out.println();
   }
  
   //function that detect the loop
   public int detectLoop() {
       Node fast=head;
       Node slow=head;
       while((fast!=null) && (fast.next!=null) && (slow!=null))
       {
           fast=fast.next.next;
           if(slow==fast)
               return 1;
           slow=slow.next;
       }
       return 0;
   }
  
   //function that create the loop
   public void createLoop() {
       Node temp=head;
       while(temp.next!=null) {
           temp=temp.next;
       }
       temp.next=head;
   }
}

public class LinkedList {
   public static void main(String args[])
   {
       Scanner sc=new Scanner(System.in);
       LinkedListImplementation list=new LinkedListImplementation();
       char ch;
       // insert the element in the linked list
       do {
           System.out.print("Enter the node");
           int el=sc.nextInt();
           list.Insert(el);
           System.out.print("Want to insert more than press Y/N");
           ch=sc.next().charAt(0);
       }while(ch=='y'||ch=='Y');
       System.out.println("Linked List ");
       // display the linked list
       list.displayList();
      
       System.out.println(list.detectLoop());//when loop is not created
       list.createLoop();//create the loop
       System.out.println(list.detectLoop());// after loop has been created
      
   }

  
}