6

I read about loop in linked list detection algorithm and I doubt

1) How to detect the "meeting element". For example, in the follow case - how to detect that the meeting is at the 3nd element?

enter image description here

2) How to detect the list's length (in case above - 6)

Both questions in running time O(n) , memory O(1).

Community
  • 1
  • 1
URL87
  • 10,667
  • 35
  • 107
  • 174
  • 2
    Very detailed answer here: http://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work – sukunrt Sep 06 '12 at 12:13

3 Answers3

9

Using tortoise-hare algorithm(floyd's cycle detection), we can find the loop in a given a list.

i.e If we move two pointers, one with speed 1 and another with speed 2, they will end up meeting if the linked list has a loop. Why? Think about two cars driving on a track—the faster car will always pass the slower one!

The tricky part here is finding the start of the loop. Imagine, as an analogy, two people racing around a track, one running twice as fast as the other. If they start off at the same place, when will they next meet? They will next meet at the start of the next lap.

Thus, after identifying the loop, if we move n1 back to Head and keep n2 at MeetingPoint, and move them both at the same pace, they will meet at LoopStart(Meeting Element).

Then, to find the length, when moving n1 back to head define a length variable. Now increment length variable on each move. After idetifying LoopStart, keep n1 ptr as such and move the n2 ptr and inc length for each move. When n2->next == n1, return the length.

This would have running time O(N), Space complexity O(1)

Mohan Kumar
  • 6,008
  • 6
  • 28
  • 36
  • "Thus, after identifying the loop, if we move n1 back to Head and keep n2 at MeetingPoint, and move them both at the same pace, they will meet at LoopStart(Meeting Element)." - can you please explain it some more ? maybe give example according the attached list.. – URL87 Sep 06 '12 at 13:15
  • let’s suppose Fast Runner had a head start of k meters on an n step lap. They will meet k meters before the start of the next lap. (Why? Fast Runner would have made k + 2(n - k) steps, including its head start, and Slow Runner would have made n - k steps. Both will be k steps before the start of the loop.) – Mohan Kumar Sep 06 '12 at 13:19
  • I do what you say on the attached example and it doesn't work ... say N1 - slower , N2 - faster . first meet at 5 . N1 go to the head, N2 stay at his place . run again -they will meet at 5 , and 5 is not the cycle start element . – URL87 Sep 06 '12 at 13:40
  • No. first meet will be on 5. that's rite. after that u need to move both ptrs in same pace(one step). it will exactly meet at loop start(here 3). – Mohan Kumar Sep 06 '12 at 15:04
0

When using Floyd's cycle-finding algorithm, the fast and slow references won't meet at the third element, but instead on the fourth. Their positions start at (1,2), and move like following: (1,2) -> (2,4) -> (3,6) -> (4,4).

I'd think, that for finding out where precisely the cycle is, you need O(n) space as well as O(n) time.

Daniel Landau
  • 2,264
  • 2
  • 15
  • 19
-1

I don't think you can do this in O(n) time using only O(1) working memory.

There are n different candidates for the "meeting element" (start of cycle), while in O(1) memory, you can only record a fixed number of them. That need not be a problem if you can go around the structure many times, but if you can only check a fixed number of nodes in each traversal, you'd need to traverse the structure n times, taking O(n²) total time.

The straightforward solution is to give up on the O(1) memory requirement. Go around the loop once and store pointers to the nodes in a hash table until you hit a duplicate entry. Expected time O(n), memory usage O(n).

Fred Foo
  • 355,277
  • 75
  • 744
  • 836