How to detect a loop in a linked list

 

How to implement Single Link list is Circular ?

Here, We have implemented a Single linked list with insert,traverse, before/after insert and circular check.

Method implemented in this snippet : -

•  insert(Node node) :  Insert Node into Linkedlist
• insert(int value) : insert value into linkedlist
• insertAfter(Node node,int newValue) : Insert value after given node  ( node ).
• insertBefore(Node node,int newValue) : Insert value before given node (node) .
• getNode(int value) : retrive Node Object by given value
• isCycle() : check Linked list is Cycle or not , return boolean value
  
  
  
  

Complete code here :-

class Node {
 public Node next;
 public int data;

 public Node(int data) {
  this.data = data;
 }
}

/**
 * @author ajay kumar gupta
 *
 */
public class CycleLinkedList {

 Node head;

 public CycleLinkedList() {
 }

 public void insert(Node node) {
  Node current = head;
  if (current == null) {
   head = node;
  } else {
   while (current.next != null) {
    current = current.next;
   }
   current.next = node;
  }
 }

 /**
  * @param node
  * @param newValue
  * After which Node, new value will be store
  */
 public void insertAfter(Node node, int newValue) {
  Node current = head;
  Node newNode = new Node(newValue);
  if (current == null) {
   head = newNode;
  } else {
   while (current != node) {
    current = current.next;
   }
   newNode.next = node.next;
   current.next = newNode;
  }
 }
 // 10 20 30 40 50 60

 /**
  * @param node
  * @param newValue
  * Before which Node, new value will be store
  */
 public void insertBefore(Node node, int newValue) {
  Node current = head;
  Node newNode = new Node(newValue);
  if (current == null) {
   head = newNode;
  } else {
   while (current.next != node) {
    current = current.next;
   }
   newNode.next = node;
   current.next = newNode;
  }
 }
 public Node getNode(int data) {

  Node current = head;
  if (current.data == data) {
   return current;
  }
  while (current.next != null) {
   current = current.next;
   if (current.data == data) {
    return current;
   }
  }
  return null;
 }

 public void insert(int data) {
  if (head == null) {
   head = new Node(data);
  } else {
   Node current = head;
   while (current.next != null) {
    current = current.next;
    System.out.println(current.data + " == " + head.data);
   }
   current.next = new Node(data);
  }
 }

 /*
  * To check list is cycle, we keep two pointer i.e fast and slow, each one
  * started from head node, fast node point to node ahead to next node while slow node 
  * point to just next node. Both pointer will be running until fast and slow get equals. 
  * example :
  * 
  * List is : 10 20 30 40 50 60 
  * 
  * Head node is 10. fast node point to Node(30) initially and subsequently increment by two node 
  * but slow node point
  * to Node(20) initially and subsequently increment by one next node.
  *  
  * fast | slow
  * 30  |  20
  * 50 |  30
  * 60 |  40
  * 20 |  50
  * 40 |  90
  * 90 |  60
  * 10 |  10 // Wow match here... 
  */
 public boolean isCycle() {
  Node fast = head;
  Node slow = head;
  while (fast != null && fast.next != null) {
   fast = fast.next.next;
   slow = slow.next;
   if (fast == slow) {
    return true;
   }

  }
  return false;
 }

 public void traverse() {
  Node current = head;
  while (current != null && current.next != null) {
   current = current.next;
   System.out.printf("%d ",current.data);
  }
 }

 public static void main(String args[]) {
  CycleLinkedList c = new CycleLinkedList();
  
  Node n1=new Node(10);
  Node n2=new Node(20);
  Node n3=new Node(30);
  Node n4=new Node(40);
  Node n5=new Node(50);
  Node n6=new Node(60);
  
  c.insert(n1);
  c.insert(n2);
  c.insert(n3);
  c.insert(n4);
  c.insert(n5);
  c.insert(n6);
  // traverse CycleLinkedLink here
  c.traverse(); // 20 30 40 50 60
  System.out.println("Add New Value after n Node ");
  c.insertAfter(n5,90); // output 20 30 40 50 90 60
  c.traverse();
  
  System.out.println("Add New Value before n Node ");
  c.insertBefore(n4,100);
  c.traverse(); // output 20 30 100 40 50 90 60
  
  System.out.println(c.isCycle()); // false
  // Again, Traverse here...
  c.traverse();
  // Making CycleLinkedLink Cycle by point last next node to n1 node.
  System.out.println(" Make Cycle Linke list.");
  c.insert(n1);
  System.out.println(c.isCycle()); // true
  
  
  
 }

}