Linked List Cycle II (LeetCode 142)

The problem

You get the head of a singly linked list that may contain a cycle. Return the node where the cycle starts (the first node you visit twice when walking from the head), or None if there is no cycle. Don’t modify the list.

Input:  1 -> 2 -> 3 -> 4
             ^         |
             +---------+     (the tail 4 points back to node 2)
Output: the node with value 2

Walking from 1 you go 2, 3, 4, then back to 2. Node 2 is the entrance to the loop.

How to think about it

Start with brute force. Walk the list, storing each node in a set. The first node you see a second time is the entrance. That is O(n) time and O(n) space. The follow-up asks for O(1).

Step one is the familiar part. Run tortoise and hare exactly as in Linked List Cycle: s moves one step, f moves two. If f reaches the end, there is no cycle. If they meet, there is one. But the meeting point is somewhere inside the loop, not necessarily the entrance.

The key insight: the head and the meeting point are the same distance from the entrance. Let a be the steps from the head to the entrance, b the steps from the entrance to the meeting point, and c the cycle length. When they meet, slow has walked a + b and fast has walked twice that. Fast’s extra distance is whole laps, so a + b = k·c for some k, which rearranges to a = k·c − b. From the meeting point, walking k·c − b steps brings you round to the entrance. So if you start a new pointer at the head and step it and slow one node at a time, they meet exactly at the entrance.

Which pattern is this? Fast & slow pointers, plus the head-reset trick. The tell is “find where a cycle starts in O(1) space”.

Approach

1. Move s one step and f two steps while f and f.next exist.
2. If the loop ends without them meeting, return None.
3. When s is f, place a new pointer p at head.
4. Move p and s one step at a time until they are the same node.
5. Return p: the cycle’s entrance.

Solution

def detect_cycle_start(head):
    s = f = head
    while f and f.next:
        s = s.next; f = f.next.next
        if s is f:                                    # met inside the cycle
            p = head                                  # head is a = k*c - b from the entrance
            while p is not s: p = p.next; s = s.next  # both one step: meet at the entrance
            return p
    return None
# list [1,2,3,4] with tail linked to node val 2 -> node with val 2

Dry run

On the example (a = 1, c = 3):

It returns the node with value 2. Check the formula: a = k·c − b = 3 − 2 = 1, and indeed the entrance is one step from the head.

Complexity

• Time: O(n). Finding the meeting point takes O(n), as in cycle detection. The second walk takes a steps, which is at most n.
• Space: O(1). Three pointers.

Edge cases and pitfalls

• No cycle: f reaches the end and the function returns None.
• Cycle starts at the head (a = 0): the meeting point is k·c steps in, so p is s immediately after the reset and it returns head.
• A single node pointing to itself: both pointers meet on it after one step and it returns that node.
• Moving fast two steps in phase two is a common slip. Both pointers must move one step after the reset.
• Returning the meeting point is the wrong answer in general. It equals the entrance only by coincidence.

Related problems

• Linked List Cycle (LeetCode 141): phase one on its own.
• Find the Duplicate Number (LeetCode 287): this exact algorithm, where the entrance is the duplicate.
• Intersection of Two Linked Lists (LeetCode 160): another equal-distance trick to make two pointers meet.