Detect First Node in the Cycle in Linked List

Question

Recently, I have went through the algorithm for detecting, first node in the cycle as stated below:-

Note: This statement has been excerpted from site:-

http://javabypatel.blogspot.in/2015/12/detect-loop-in-linked-list.html

Now point is, how we will come to know the start node of a loop.
STEP 1: After finding the loop, both pointers are pointing to common node that is at meeting point inside loop,
STEP 2: Now, move one pointer among them(say tortoise) to the head of list, keeping hare pointer at the same position that is at meeting point inside loop.
STEP 3: Start moving both pointers one node at a time. The place they both will meet is the start node of the loop/cycle.

Lets consider Case 2 in the following image:-

http://4.bp.blogspot.com/-79s5PBIexDE/Vmac8UlposI/AAAAAAAAAvQ/ejHRpGv_OLY/s1600/loop-in-linked-list-example.png

While applying all steps, in the case 2, I got tucked up in Step 3

"The following is the work outs for the Hare and Tortoise algorithm against the case 2."

Faster - 1 Slower - 1
Faster - 5 Slower - 20
Faster - 22 Slower - 5
Faster - 20 Slower - 18
Faster - 18 Slower - 22
Faster - 1 Slower - 1 - Both of the pointers meet here..

So, as per STEP 2, I am keeping the Faster Pointer as it is, and moving the Slow Pointer to 1 (which is the head of the list).

So, as per STEP 3, I am incrementing each pointer one by one.

Since, both of them are in "1", moving each pointer by one, will never end and it moves on and on.

Q1. May I kindly know, whether I got understood anything wrong here in STEP 3?

Q2. May I assume that, the node where the loop is ending, is the first node in the cycle?

• Norman: See also this question. It has nice answers with pictures!

Answer 1

You seem to have traced the given algorithm correctly until the very last step. At the very last step, though, I think you mistook the term the head of list to be the pointer to the first element of the list. Consequently, you may have inferred that the loop would never end as both pointers would move at the same speed and one would be ahead of the other by 1. Yet, I believe the head of the list was used to refer to the first element in the list, not the pointer to the first element.

By the way, I do not think your confusion is rooted in a mistake made by you, but rather in an ambiguity in the pseudocode you provided in your question. Even if you did not misinterpret the head of the list, you would execute Step 3 of the pseudocode once, and conclude that the pointers would meet at node with label 20. (i.e. the one after the first node of the list) So, I think Step 3 could use some clarification as the following.

STEP 3: While hare and tortoise are at different cells, move both pointers one node at a time.

Corrected like this, if a case like case 2 you provided is encountered, after moving one of the pointers to the beginning of the list, the condition to iterate will not be fulfilled, as the pointers have already met. (due to the start of cycle being at the beginning of the list)

Even though your original Q2 was quite unclear, let me answer to it based on your clarifications to it as comments to my answer.

enter image description here

In the link you provided, it is shown that the meeting point M the hare and the tortoise pointers meet after Step 1 of the pseudocode you provided has the exact distance to the start of the loop as the first element of the list has. (i.e. distances p and r in the diagram above are equal) Consequently, if one pointer is placed at the beginning of the list and the other remains at their meeting point, if both move by 1 as long as they are not at the same node of the list, yeah, you may assume where they meet will be the beginning of the loop in the list, if such a loop ever exists.

• NANDAKUMAR THANGAVELU: Hi, Whether my understanding is right on the Q2. Some advice pls. Thanks.
• ilim: Can you clarify which loop you are referring to in your Q2? Is it the first loop where hare goes by 2 and tortoise goes by 1, or is it the loop described in Step 3 of the pseudocode you provided where both hare and tortoise go by 1?
• NANDAKUMAR THANGAVELU: Hereby, I meant the "tortoise" loop. 1. Generally, by looking any question which is having the loop like this, can I come to conclusion, that the first node in the cycle is, the ending of Tortoise loop? 2. And Hereby, I can not take the Hare Pointer, since it may jump outside or inside or exactly on the "1" right?... Thanks..
• ilim: Updated my answer to clarify the answer to the question #1 you asked in your latest comment. As to your question #2 in the same comment, whether you move the hare or the tortoise pointer to the beginning of the list does not make any difference. In the last loop, both hare and tortoise moves by 1.
• robert: The diagram suggests one could count steps during the first phase, and then walk half that many from the head to reach the first looped node (the node with two predecessors). This would not work. The hare may have cycled through the loop many times before the tortoise catches up.