Wednesday, January 25, 2017

Detect a cycle in linked list

The problem is to detect a cycle in a linked list, and find a start node of the cycle.
We have a linked list.






First, we have to know how many nodes in the cycle. To find out, we use two pointers with different speed and stop when the node is the same. Then use only one pointer and move forward, and save current node and count the node, then stop when the pointer is in the same node.
Second, use two pointers, each apart the the number of nodes in the cycle. When we met the same node while moving two pointers, that is the start node of the cycle.
Complete source in Java is in the below.


 import java.io.*;
 class myCode
 {
   public static void main (String[] args) throws java.lang.Exception
   {
     System.out.println("Hello Java");
     myCode code = new myCode();
     code.doWork();
   }
   public void doWork() {
     Node node = new Node(1);
     Node temp1 = new Node(2);
     Node temp2 = new Node(3);
     Node temp3 = new Node(4);
     Node temp4 = new Node(5);
     node.next = temp1;
     temp1.next = temp2;
     temp2.next = temp3;
     temp3.next = temp4;
     temp4.next = temp2;
     int cycle = detect(node);
     int start = findStart(node,cycle);
     System.out.println(cycle);
   }
   public int detect(Node head) {
     Node first = head;
     Node second = head;
     int count = 0;
     boolean found = false;
     while (first != null && second.next != null) {
       first = first.next;
       second = second.next.next;
       if (first.value == second.value) {
         found = true;
         break;
       }
     }
     if (found) {
       int start = first.value;
       while (first != null) {
         first = first.next;
         count++;
         if (first != null && first.value == start) {
           return count;
         }
       }  
     }
     return -1;
   }
   public int findStart(Node head, int cycle) {
     Node first = head;
     Node second = head;
     for (int i=0;i<cycle;i++) {
       second = second.next;
     }
     while (first.value != second.value) {
       first = first.next;
       second = second.next;
     }
     return second.value;
   }
   class Node {
     int value;
     Node next = null;
     public Node(int val) {
       value = val;
     }
   }
 }

No comments:

Post a Comment