Finding start of cycle in linked list

Question

I have a doubt related to a leetcode question (Linked List Cycle II), whose solution is listed here. Specifically I want to ask about the following code block in the solution:

node1, node2 = head, hare
while node1 != node2:
 node1 = node1.next
 node2 = node2.next
return node1

After the tortoise and the hare meet, we need to find where the cycle starts in the linked list, so two pointers are started, one from the head and the other from the hare. My question is that why does this code block always work ? Why isn't there a situation where the node2 may end up being always one step behind node1 ?

Answer 1

Two steps here. First we show what the solution implies algebraically, and then we show that the solution exists. This is "going" backwards and then forward again - I assume that the solution above is true, check what are the implications, and prove that they can occur.

I'm not sure there is an easy intuition arising from the proof below. I for one can't see something that would be trivial to deduce.

Step 1

Denote our nodes 0...L, the cycle start point as C, and the first meeting point of the hare and the tortoise (can we just say turtle?), if it exists, as M.

Lemma 1 M = (L-C)J where J is some Integer.

This comes from looking at what the hare passed:

1. The total distance is just 2M, since the tortoise waked M nodes (this is where setting the starting point is 0 starts to pay off, otherwise we would need -1s everywhere).
2. On the other hand, the hare arrived at M, and then kept going through L-C length cycles. If it bothers you it might "miss" M in a few runs, remember it doesn't matter - in the end it gets to M, and you can go backwards by single steps, unwinding an integer amount of cycles, then going back from M to 0.

So:

2M = M+(L-C)J => M = (L-C)J

and we're done.

Lemma 2 If M exists, C = (L-M) + (L-C)I where I is some integer.

This is easier. Again we look at what the two nodes have to pass. The head has to pass precisely C (LHS), while the node at the meeting point has to get to L from M, and then one more to get to C. Since we are 0 counting, this ends up as L-M. Now it has to go through L-C an integer amount of cycles, proving the above.

Step 2

Now we show the solution exist.

Lemma 3 J from Lemma 1. exists such that L >= M >= C.

If there exists a J such that (L-C)J = C we are done. Otherwise, take the smallest K such that

(L-C)K > C

assume by negation that

(L-C)K > L => (L-C)K - (L-C) > L - (L-C) => (L-C)(K-1) > C

contradicting the assumption K was minimal. Thus, J=K solves our problem.

Lemma 4 I from Lemma 2 exists.

To see this we merely need to see if there is a solution to C = (L-M)I where I and J are Integer and positive. We substitute M and have:

C = (L-M) + (L-C)I = L-(L-C)J+(L-C)I = (1-J+I)L + (J-I)C => (1-J+I)L=(1-J+I)C

So if there is to be an integer solution, either L=C, which is uninteresting, or

I=J-1

Q.E.D