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(n2) 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.
-
actually I should have mentioned without using hash. thanks for pointing outJavaDeveloper– JavaDeveloper08/25/2013 03:13:40Commented Aug 25, 2013 at 3:13
-
@MitchWheat I have heard the linked list question phrased with the same restriction. This makes the question a little more difficult.isaach1000– isaach100008/25/2013 03:17:38Commented Aug 25, 2013 at 3:17
-
There's a lot of good answers for this question on StackOverFlow. Here's my favorite: stackoverflow.com/questions/2663115/…dcaswell– dcaswell08/25/2013 03:24:06Commented Aug 25, 2013 at 3:24
-
This is not 'loop detection' the question is about finding the point of the loop, with 2 nodes pointing to it.JavaDeveloper– JavaDeveloper08/25/2013 03:28:09Commented Aug 25, 2013 at 3:28
2 Answers 2
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?
-
This algorithm is known as "Floyd's cycle-finding algorithm" or simply "tortoise and the hare".yasen– yasen08/25/2013 03:25:38Commented Aug 25, 2013 at 3:25
-
Thanks thats over the surface very logical. we have covered half the distancer by slow pointer, assuming E was the end of the linkedlist.JavaDeveloper– JavaDeveloper08/25/2013 03:27:05Commented Aug 25, 2013 at 3:27
-
@JavaDeveloper I have added link for the mathematical proof.Ensure to read that.Algorithmist– Algorithmist08/25/2013 03:32:26Commented Aug 25, 2013 at 3:32
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.
Explore related questions
See similar questions with these tags.