How to find loop-node of a linkedlist with a loop?

Question

This question is a bit different than finding an intersection of 2 linked lists.

Consider a linkedlist with a loop: A - B - C - D - E - F - C.

If node A is the input to the function, then it should return C.

Since I do not know what to call C, I have used a term loop-node C as seen in the question. Although an O(n²) term appears obvious, can there be a way to find loop-node with lesser complexity?

A hash table / extra space of O(n) not allowed.

• JavaDeveloper: actually I should have mentioned without using hash. thanks for pointing out
• isaach1000: @MitchWheat I have heard the linked list question phrased with the same restriction. This makes the question a little more difficult.
• dcaswell: There's a lot of good answers for this question on StackOverFlow. Here's my favorite: stackoverflow.com/questions/2663115/…
• JavaDeveloper: This is not 'loop detection' the question is about finding the point of the loop, with 2 nodes pointing to it.

Answer 1

There is a simple approach using two pointers.First pointer increments by one and second by twice the speed of slow pointer.

So linked list in your case is actually A->B->C->D->E->F->C meaning F points back again to C.So approach is like below

1.Keep on incrementing the two pointers till they match.So in above case we would have these set of steps

Slow Pointer: A B C D E
Fast Pointer: A C E C E

So we stop at E and which indicates that there is a loop.Now we need to find the loop node.

Now from E move the slow pointer to the beginning of the linked list and create a new pointer which points at E and also increments by 1.The point at which these two pointer meet is actually the loop node.So in our case

Pointer From the Beginning: A B C New Pointer: E F C

So as you see they meet at C and we are done with finding the loop node in a linked list.

Update: For the Mathematical proof of this approach please refer this wonderful question and see @Jim Lewis answer alongwith all the comments beneath the answer. Explain how finding cycle start node in cycle linked list work?

• yasen: This algorithm is known as "Floyd's cycle-finding algorithm" or simply "tortoise and the hare".
• JavaDeveloper: Thanks thats over the surface very logical. we have covered half the distancer by slow pointer, assuming E was the end of the linkedlist.
• Algorithmist: @JavaDeveloper I have added link for the mathematical proof.Ensure to read that.

Answer 2

Floyd's cycle-finding algorithm is the simplest one, and often the "canonical answer" because it's what everyone learns in university (perhaps because it is simple, elegant, and insightful).

It is also often claimed that the runtime is not improvable, but that is not so - the big Oh might not be improvable, but that only tells us something about the asymptotic behavior in the worst case. Brent's algorithm is faster in practice, while still using a constant amount of space. There are more algorithms, such as Gosper's Loop Detection or Sedgewick, Szymanski, and Yao's algorithm or the k-stacks algorithm, that all use a certain (low, but non-constant in theory) amount of space. Actually the amount of space will still be constant for any practical implementation of linked lists, because your pointers will be fixed size. For example, with 32 bit pointers, Gosper's Loop Detection would use 33 words of space (plus maybe a couple extra, depending on what you want to count).

Floyd's algorithm is nice, but not necessarily The Answer^(tm). There are choices and trade-offs to be made.