Finding a 'circle' in a linked list

You have n numbrer Node objects - could be 1,000,000 for all you know. Each Node has a getNext() method that returns the next Node (a linked list).

But the chain of n number of Node objects linked together by the getNext() method, somewhere in the chain, points back to a Node earlier in the chain so if you keep calling getNext() to walk the chain you will never get to the last Node - it will loop forever.

What is the best way to determine if this linked list of Node objects has a 'circle' and extra points if you can tell where in the chain does it occur i.e. what is the Node that is returing an earlier Node in the chain?

Questions by wcmaggot

Showing Answers 1 - 3 of 3 Answers

doddaiah

  • Jun 21st, 2009
 

Take two pointers P1 and P2.


Initially let P1 and P2 point to starting node (S) and set counter to zero.
increment the counter
then check 
while(1) {

if p1 == p2 ->next
{
   print the counter value this is the node where circle starts.
   exit();
}

else {
    increment the counter; 
    p1 = p2;
    p2 = p2->next;
    if ( S == p2 )
    exit(); if Staring node is equal to P2 then we have reached end of list. 
}

}

kaushurtz

  • Mar 2nd, 2010
 

There are many ways to find loops in linked list but the best one is known as tortoise and hare algorithm.
In this we take 2 nodes say slow and fast node. Then we move the slow node by one shift ie startNode.next and the fast node with 2 shifts and then compare both slow and fast node. If they come to be equal at any time while iteration then this indicates that the linked list has a loop.

  Was this answer useful?  Yes

Beniskickbutt

  • Dec 22nd, 2014
 

p1 == p2->next will only work if your circle only encompasses 2 elements of your list.
Also, S == p2 will never be true (causing an infinite loop) if you dont have a circular list to begin with

  Was this answer useful?  Yes

Give your answer:

If you think the above answer is not correct, Please select a reason and add your answer below.