2

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.

Algorithmist
6,7037 gold badges37 silver badges50 bronze badges
asked Aug 25, 2013 at 3:04
4
  • actually I should have mentioned without using hash. thanks for pointing out Commented 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. Commented 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/… Commented 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. Commented Aug 25, 2013 at 3:28

2 Answers 2

6

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?

Anshika Singh
1,05414 silver badges20 bronze badges
answered Aug 25, 2013 at 3:19
3
  • This algorithm is known as "Floyd's cycle-finding algorithm" or simply "tortoise and the hare". Commented 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. Commented Aug 25, 2013 at 3:27
  • @JavaDeveloper I have added link for the mathematical proof.Ensure to read that. Commented Aug 25, 2013 at 3:32
0

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.

answered Aug 25, 2013 at 12:48

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.