LeetCode 142 · Linked list

Linked List Cycle II, explained with a picture

Where does the loop begin?.

Linked list
▶ Watch it step by step

The problem

If a linked list has a cycle, return the node where the cycle begins; otherwise return none.

Input:  3 → 2 → 0 → −4 → 7, last links back to position 1
Output: position 1

Picture it

Picture the tortoise and hare on a looping track. After they meet inside the loop, put the tortoise back at the start. Now both walk one step at a time; the point where they meet again is exactly where the loop begins (a neat consequence of the distances involved).

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Floyd’s algorithm, phase two: reset one pointer to head and walk both at speed 1.

Python solution

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow, fast = slow.next, fast.next
            return slow
    return None

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.