LeetCode 142 – Linked List Cycle II

Linked List Cycle asked whether there is a cycle. This asks where it starts, and the answer is a genuinely surprising piece of arithmetic: after the pointers meet, put one back at the head, walk both one step at a time, and they meet again exactly at the cycle's entrance. It looks like a coincidence. It is four lines of algebra.

The problem

Return the node where the cycle begins, or null if there is no cycle. Do not modify the list. The follow-up asks for O(1) space.

3 -> 2 -> 0 -> -4        -> the node holding 2
     ^          |
     +----------+

1 -> 2 -> back to 1      -> the node holding 1
1 (no cycle)             -> null
[]                       -> null

The algebra

Name the pieces:

t = steps from head to the cycle entrance
c = cycle length
m = steps from the entrance to the meeting point

head ---- t ----> [entrance] ---- m ----> [meeting] ...back round... 
                       ^                                            |
                       +--------------------- c ---------------------+

When they meet, the slow pointer has taken t + m steps and the fast has taken twice that. The fast pointer's distance is also t + m plus some whole number of extra laps:

2(t + m) = t + m + k·c        for some integer k ≥ 1
     t + m = k·c
         t = k·c - m

Read the last line aloud: the distance from the head to the entrance equals the distance from the meeting point onward to the entrance (going round the cycle, possibly several times). So a pointer starting at the head and a pointer starting at the meeting point, both moving one step at a time, arrive at the entrance together.

That derivation is the answer. Anyone can memorise "reset one to the head"; being able to produce t = k·c - m is what separates recall from understanding, and it takes about forty seconds on a whiteboard.

Java

class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                // Phase 2: t = k*c - m, so these two meet at the entrance.
                ListNode walker = head;
                while (walker != slow) {
                    walker = walker.next;
                    slow = slow.next;
                }
                return walker;
            }
        }

        return null;      // fast fell off the end: no cycle
    }
}

Phase 2 lives inside the detection loop, entered only on a meeting. Putting it after the loop would need a separate flag to distinguish "met" from "ran off the end", and that flag is where this gets written wrong.

while (walker != slow) and not a fixed number of steps: neither t nor c is known, and the algorithm never needs to compute them. That is the elegant part — the arithmetic justifies the loop but never appears in it.

A cycle starting at the head works: t = 0, and walker != slow is false immediately, so head is returned without either pointer moving.

Python

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow is fast:                  # identity, as in problem 141
                walker = head
                while walker is not slow:     # t = k*c - m
                    walker = walker.next
                    slow = slow.next
                return walker

        return None

If you cannot reproduce the algebra

Say so and use the hash set. Walking the list and returning the first node already seen is correct, obvious and O(n) space:

seen = identity set
for node in list:
    if node in seen: return node
    seen.add(node)
return null

A working O(n)-space solution you can explain beats a half-remembered O(1) one you cannot. If the interviewer wants the constant-space version they will ask, and then you can derive it rather than reciting it.

Complexity

Phase 1 meets within t + c ≤ n steps, and phase 2 takes exactly t more. Both linear, so the whole thing is O(n) with a small constant.

Where else this appears

Find the Duplicate Number (287) is this problem in disguise and is the reason it is worth knowing properly. An array of n+1 values in 1..n defines a successor function i → nums[i]; a repeated value means two indices share a successor, which is a cycle, and its entrance is the duplicate. That gives an O(n)-time, O(1)-space answer to a problem that otherwise seems to need sorting or a hash set — and it is the same code with next replaced by an array lookup.

Happy Number (202) uses phase 1 only, on the sequence n → sum of squared digits.

What the interviewer is checking

• That you can derive t = k·c - m rather than assert the reset.
• That phase 2 is entered only on a meeting, with no extra flag.
• That the loop compares nodes rather than counting steps.
• A cycle starting at the head, returning the head.
• No cycle, empty list, single node.
• Identity comparison, not value equality.
• That you would rather give a clear hash-set answer than a shaky clever one.