Leetcode 142: Linked List Cycle II

This question is asking for the node where the cycle begins if there’s any, without modifying the list. It may comes less intuitive at the first glance, therefore we need some kind of algorithms that can detect the cycle in a different way.

Floyd’s cycle-finding algorithm

The idea of this algorithm came up by Robert W. Floyd, is by using two pointers (tortoise and hare), such that one moves twice faster (2x speed) than the other, if there exists a cycle, the pointers will eventually meet at a certain point >= where the cycle starts.

Following the algorithm, consider the singly linked list with a cycle like this:

*(Suggest drawing it out to make this clear :D)

Head _ _ _ {x}_ _ _ Cycle(S)_ _ _ {y}_ _ _ Meeting point(M)_ _ _ {z}_ _ _ Cycle(S)_ _ _ _

We know that at the meeting point (M), the distance travelled by the tortoise (the slow pointer) will be x + y, and for the hare (the fast pointer) will be x + y + z + y = x + 2y + z. Since we know the time is constant and the hare moves 2x speed than the tortoise, therefore we can deduce:

2 * (x + y) = x + 2y + z

2x + 2y = x + 2y + z

2x = x + z

x = z

Which means Distance (Head to Cycle start) equals to Distance (Meeting point to Cycle start).

Another way to prove the same statement:

Head _ _ _ {x} _ _ _ Cycle(S) _ _ _ {?} _ _ _ Meeting point(M) _ _ _ {?} _ _ _ (2x) _ _ _ {y} _ _ _ Cycle(S) _ _ _

Assuming the distance between the Head and Cycle(S) is x, when the tortoise arrives at Cycle(S), the hare will be at 2x. Assuming the distance between 2x and Cycle(S) by going forward is y, when the hare reaches Cycle(S) again by following the cycle, the tortoise will be at x + y/2.

So the problem now becomes:

The hare moves 2x faster than the tortoise, the distance between them now is a certain value say y/2, when will the hare catch the tortoise?

And the answer is when the hare moves y distance, after a time of y/2.

If we think about where the hare starts, it’s actually Cycle(S), and after y distance, they will meet, so the meeting point is at x + y.

We know that 2x to Cycle(S) is y, and Distance (Meeting point to 2x) is 2x - (x + y) = x - y, and so Distance (Meeting point to Cycle(S)) is x - y + y which is x itself.

The other case happens when the meeting point occurs before 2x:

Head _ _ _ {x} _ _ _ Cycle(S) _ _ _ (2x) _ _ _ Meeting point(M) _ _ _ {?} _ _ _ Cycle(S) _ _ _

We can still follow the same logic and find out the meeting point is at x + y. And the distance from 2x to the meeting point will be x + y - 2x = y - x. With the fact the distance between 2x and Cycle(S) by going forward is y, Distance (Meeting point to Cycle(S)) will be y - (y - x) which is x itself.

By knowing Distance (Head to Cycle start) equals to Distance (Meeting point to Cycle start), once we detect the tortoise and the hare pointers meet, we can have a pointer starting from the head that moves with a one in the meeting point at the same speed, and the point they meet up will be Cycle(S), the start of the cycle.

Summary

1. The slow and fast pointers (tortoise and hare) will meet up if there exists a cycle, otherwise the fast pointer will reach a None node.

2. When they reach at the meeting point, one moves from the head with the slow pointer moves from the meeting point at the same speed, the point they meet up is the start of the cycle.

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return None

        slow = head.next
        fast = head.next.next

        while fast != slow:
            if fast is None or fast.next is None:
                return None

            slow = slow.next
            fast = fast.next.next

        fast = head
        while slow != fast:
            fast = fast.next
            slow = slow.next

        return slow