Linked List Cycle II

Knowing that a list loops is often not enough. To break the loop, or to report where a chain of references goes wrong, you need the exact node where the cycle begins. This is the follow-up to Linked List Cycle, and it is where interviewers ask for the proof.

The problem

Given the head of a singly linked list, return the node where its cycle begins: the first node you reach twice when walking from the head. If there is no cycle, return None. Do not change the list.

• 1 → 2 → 3 → 4 → 5 → 6, where node 6 points back to node 3 → the node holding 3.
• 8 → 8, where the second node points back to the first → the first node (the head). Values repeat, so returning "the node with value 8" is ambiguous; you return the node object.

Constraints: up to 10⁴ nodes; the follow-up asks for O(1) extra memory.

Clarifying questions

• Return the node or its value? The node. Values can repeat.
• Can I modify the list? No. Tricks that mark visited nodes are out.
• What if there is no cycle? Return None.

Approach 1: the first node seen twice

Walk the list, adding each node to a set. The first node that is already in the set is the entrance, because it is the first place the walk comes back to.

1def detect_cycle_with_set(head: ListNode | None) -> ListNode | None:2    """The first node seen twice is the entrance."""3    seen: set[ListNode] = set()4    node = head5    while node is not None:6        if node in seen:7            return node8        seen.add(node)9        node = node.next10    return None

Time: O(n). Space: O(n) for the set. This is correct and fast, but it breaks the O(1)-memory follow-up.

The key insight

Phase 1 of Floyd's algorithm finds a node inside the cycle: the meeting point. It is usually not the entrance. The insight is an equation that tells you how far the meeting point is from the entrance.

Name the distances. a is the number of steps from the head to the entrance. L is the cycle length. b is the number of steps from the entrance forward to the meeting point. On our example list, a = 2 (1 → 2 → 3), L = 4 (3 → 4 → 5 → 6 → 3), and, as the dry run shows, they meet at node 5, so b = 2.

At the meeting, slow has walked a + b steps. Fast has walked twice as far, and fast's path is slow's path plus some whole number k of extra laps:

2(a + b) = a + b + kL   a + b = kL       a = kL − b

Now read a = kL − b as a walk. Start at the meeting point, which is b steps into the cycle. Walk kL − b steps: L − b of them finish the current lap and bring you to the entrance, and the remaining (k − 1)L are whole laps that bring you back to it. So a steps from the meeting point lands on the entrance. And a steps from the head lands on the entrance too, by definition.

That gives the algorithm: after they meet, send one pointer back to the head and move both one step at a time. After exactly a steps they stand on the same node, and that node is the entrance. You never need to know a, b or L.

Approach 2: two phases

1. Phase 1. Run slow (1 step) and fast (2 steps) from the head. If fast reaches the end, return None.
2. Phase 2. When they meet, set walker to the head. Move walker and slow one step each until they are the same node.
3. Return that node.

1def detect_cycle(head: ListNode | None) -> ListNode | None:2    """Return the node where the cycle begins, or None. O(n) time, O(1) space."""3    slow = fast = head4    while fast is not None and fast.next is not None:5        slow = slow.next6        fast = fast.next.next7        if slow is fast:                 # phase 1: they met inside the cycle8            walker = head                # phase 2: one pointer back to the head9            while walker is not slow:10                walker = walker.next     # both move ONE step11                slow = slow.next12            return walker13    return None

Dry run on 1 → 2 → 3 → 4 → 5 → 6, with 6 pointing back to 3:

Phase 2 took 2 steps, which is a, as the equation predicts. Here k = 1: fast did one extra lap, and a = 1 × 4 − 2 = 2.

Time: O(n). Phase 1 takes fewer than a + L ticks, as in Linked List Cycle. Phase 2 takes exactly a ticks. Both are at most n. Space: O(1).

Edge cases

• No cycle. Phase 1 ends with fast at the end; return None.
• Cycle starts at the head (a = 0). They meet at the head itself, since kL − b = 0 means b is a whole number of laps. Phase 2's loop condition is false at once and the head is returned.
• Self-loop on one node. Tick 1: slow and fast are both on that node. walker is the head, which is the same node, so it is returned with no phase-2 steps.
• Long tail, short loop. If a is much bigger than L, fast laps the cycle many times before slow arrives, so k is large. The equation still holds; phase 2 simply walks the whole tail.

Follow-ups

• "What is the cycle length?" From the meeting point, step one pointer round until it returns, counting: that is L.
• "Remove the cycle." Find the entrance, then walk from it round the loop until you reach the node whose next is the entrance. Set that node's next to None.
• "Find where two lists intersect." Join the end of list A to its head, then run this algorithm from list B's head; the entrance is the intersection. Undo the join afterwards. (The simpler answer is two pointers that switch lists at the end.)