Monday, 24 October 2016

Find start of the loop in the linked list using Java...

Problem Statement:- Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.
DEFINITION:-
Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.

EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C

here is the code ...


       
public class Q5 {

 public static void main(String[] args) {

  Node head = new Node(1);    // head node of the linked list
  Node node1 = new Node(2);
  head.next = node1;
  Node node2 = new Node(3);
  node1.next = node2;
  Node node3 = new Node(4);
  node2.next = node3;
  Node node4 = new Node(5);
  node3.next = node4;
  Node node5 = new Node(6);
  node4.next = node5;
  Node node6 = new Node(7);
  node5.next = node6;
  node6.next = node3;        // here loop appears
  findNodeAtbeg(head);
 }

 public static void findNodeAtbeg(Node head) {
  Node slow = head;          //slow pointer
  Node fast = head;          //fast pointer

  while (fast != null) {
   slow = slow.next;
   fast = fast.next.next;
   if (slow == fast) {
    break;
   }
  }
  if (fast == null) {
   System.out.print("There is no loop exit");
  }
  slow = head;
  while (slow != fast) {
   slow = slow.next;
   fast = fast.next;
  }
  System.out.println("Node where loop begins contains data item as - "
    + fast.data);
 }
}

class Node {
 int data;
 Node next;

 Node(int d) {
  data = d;
  next = null;
 }
}