L20 · Linked Lists II — Cycles, Middle, Reorder

Series: LeetCode — From Basics to Interview-Ready · Session 20 / 65 · Phase 1 · Core patterns

Why this session exists

Reorder List is find-middle plus reverse plus merge. It is not a new algorithm; it is three primitives you already own, executed in sequence. That composition is the actual lesson of this session, and it generalises far beyond linked lists.

The new primitive here is the slow-fast pointer pair. Two pointers moving through the same list at different speeds gives you three things for free: whether the list has a cycle, where that cycle begins, and where the midpoint is — all in one pass with constant space. Those are three different-looking questions with one mechanism underneath.

Floyd's algorithm also carries something rarer in interview prep: a proof short enough to reproduce under pressure and non-obvious enough to be worth reproducing. Being able to derive why the entry point is found by restarting one pointer at the head — rather than asserting it as a memorised rule — is a genuine signal. Most candidates know the trick; far fewer can say why it works.

Blank-file warm-up

Five minutes, empty file, no notes. Write:

1. The slow-fast loop that detects a cycle, including the exact while guard.
2. Given a meeting point inside the cycle, the additional loop that returns the cycle entry node.
3. The slow-fast loop for the midpoint — and state which node slow ends on for even length under each of the two possible loop guards.

That third item is where people are vague. while fast and fast.next and while fast.next and fast.next.next give different midpoints on even-length lists, and Reorder List depends on which one you pick.

Pattern anatomy

The shape that summons this pattern: a positional question about a list you cannot index into, answered without a length precomputation.

Cycle detection. Invariant: fast advances exactly two nodes for every one that slow advances, so the gap between them grows by one per step.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:      # both guards needed: fast.next.next must be legal
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False                   # fast reached the end -> no cycle

If there is no cycle, fast reaches the end and the loop exits — the guard fast and fast.next is what makes this safe, and both halves are required. If there is a cycle, both pointers are eventually inside it, the gap closes by one per step, and since the cycle is finite the gap must reach zero. They cannot step past each other, because a gap of one becomes a gap of zero on the next step, not a gap of minus one.

Cycle entry. Let L be the distance from head to the cycle entry, C the cycle length, and m the distance from the entry to the meeting point measured along the cycle.

When they meet, slow has travelled L + m (assuming it entered the cycle and met before completing a lap, which holds because fast gains one position per step and the cycle length is C). fast has travelled exactly twice that: 2(L + m). The difference, L + m, must be a whole number of laps: L + m = kC for some positive integer k.

Rearranged: L = kC - m. Read that as a claim about walking: starting at the head and walking L steps lands you at the entry. Starting at the meeting point and walking L steps means walking kC - m steps, which from a point that is m past the entry brings you to exactly kC — a whole number of laps — landing you at the entry as well.

So: reset one pointer to the head, advance both one step at a time, and they meet at the entry.

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:                    # cycle confirmed
            p = head
            while p is not slow:
                p = p.next
                slow = slow.next
            return p                        # the entry node
    return None

Midpoint. Same mechanism, no cycle. When fast reaches the end, slow is at half the distance.

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow          # for even length, this is the SECOND middle node

For [1,2,3,4] this returns node 3. Changing the guard to while fast.next and fast.next.next and starting both at head returns node 2, the first middle. Reorder List and Palindrome want the first middle so that the second half is no longer than the first — pick deliberately, and trace a four-element list to confirm which one you got.

The composition. Reorder List L0 → L1 → ... → Ln into L0 → Ln → L1 → Ln-1 → ...:

def reorder_list(head):
    if not head or not head.next:
        return
 
    # 1. split at the FIRST middle
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    second = slow.next
    slow.next = None               # sever, or you build a cycle
 
    # 2. reverse the second half
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt
 
    # 3. interleave
    first, second = head, prev
    while second:                  # second is never longer than first
        f_next, s_next = first.next, second.next
        first.next = second
        second.next = f_next
        first, second = f_next, s_next

Three phases, each independently testable, none of them new. slow.next = None in phase 1 is the line people forget, and omitting it creates a cycle in phase 3 that manifests as a hang rather than a wrong answer.

The cue

How you recognise this from the problem statement:

1. "Cycle", "loop", "does it terminate". Floyd. Also applies outside linked lists — Find the Duplicate Number is Floyd on an implicit array-as-function graph.
2. "Middle node", "second half", "first half". Slow-fast, one pass, no length count.
3. "Palindrome" or "reorder" on a linked list with O(1) space. The space constraint is the tell: it rules out copying to an array and forces split-reverse-compare.
4. "Nth from the end", "kth from last". Fixed-gap two pointers, from the previous session.
5. An operation described in terms of both halves interacting. Reorder, palindrome check, "merge with its own reverse" — all are split-reverse-then-pairwise.

The anti-cue: if the problem lets you use O(n) space and does not care about elegance, converting to a list of nodes and indexing directly is faster to write and impossible to get wrong. Say that you are choosing the pointer version because of the stated constraint, not because it is clever.

Guided solve

Linked List Cycle II. Given the head of a list, return the node where the cycle begins, or None if there is no cycle. Constraint: O(1) space.

The O(n) solution is immediate — walk the list, put every node in a set, return the first one seen twice. Say it, then say that the space constraint rules it out.

Phase 1 is plain detection. The one detail that matters is the guard: while fast and fast.next. You need fast non-null to read fast.next, and fast.next non-null to read fast.next.next. Drop either and an acyclic list of even length crashes on a null dereference.

Phase 2 is the entry location, and this is where the derivation matters. Take a concrete list: 1 → 2 → 3 → 4 → 5 → 6 → 3 (node 6 links back to node 3). So L = 2 (head to node 3, the entry), C = 4 (nodes 3, 4, 5, 6).

• Step 1: slow at 2, fast at 3.
• Step 2: slow at 3, fast at 5.
• Step 3: slow at 4, fast at 3 (fast wrapped: 5 → 6 → 3).
• Step 4: slow at 5, fast at 5. Meet.

Meeting node is 5. Distance from entry (node 3) to meeting point (node 5) along the cycle is m = 2. Check the identity: slow travelled 4 steps, and L + m = 2 + 2 = 4. Fast travelled 8, which is 2(L + m). The difference is 4, exactly 1 × C. So k = 1 and L = kC - m = 4 - 2 = 2. Correct.

Now reset p to head and step both:

• p at 1, slow at 5.
• p at 2, slow at 6.
• p at 3, slow at 3. Equal. Return node 3 — the entry.

Two steps, exactly L. The derivation predicted it.

The edge cases to verify before you say done: empty list returns None immediately since fast is None. Single node with no cycle — fast.next is None, loop does not run, return None. Single node pointing at itself — slow and fast both move to the same node and meet, then p starts at head which is that node, so the second loop exits immediately and returns it. All correct with no special cases.

Solo timed

15 minutes each, timer visible.

• Reorder List — split at the first middle (guard on fast.next and fast.next.next), sever with slow.next = None, reverse the second half, then interleave. Test on a four-element list and a five-element list; the odd case is where an off-by-one in the split shows up.
• Palindrome Linked List — same split and reverse, then walk both halves comparing values. Bonus points for restoring the list afterward, which is a real code-review concern: a predicate function that mutates its input is a bug waiting to happen.

If you finish early: solve Find the Duplicate Number using Floyd, treating nums[i] as a pointer from node i to node nums[i]. It is the same algorithm on a different substrate and it is worth seeing once.

Common failure modes

Guard missing a half. while fast alone crashes on fast.next.next when fast.next is None. Both conditions, in that order — short-circuit evaluation is doing the protecting.

Using == instead of is. Value equality reports a cycle where none exists if two nodes hold the same value. Identity comparison is what the algorithm means.

Forgetting to sever the halves. slow.next = None before reversing the second half. Skip it and the interleave phase builds a cycle; the symptom is a hang or a memory blowup, not a wrong answer, which makes it slower to diagnose.

Wrong midpoint for even lengths. Reorder needs the second half to be no longer than the first. Getting the second middle instead of the first leaves an extra node in the wrong place, and the failure appears only on even-length inputs.

Starting the entry-finding loop from the wrong node. It must be head. The identity L = kC - m is a statement about distance from the head specifically.

Interleaving past the end. In phase 3, loop on second, not on first. After the split, the first half is the same length or one longer, so second exhausts first and is the correct loop condition.

Complexity

Cycle detection — Time: O(n), Space: O(1). Before entering the cycle, slow takes L steps. Inside the cycle, the gap closes by one per step and is at most C, so at most C more steps. Total is bounded by L + C ≤ n. Only two pointer variables.

Cycle entry — Time: O(n), Space: O(1). The second phase runs exactly L steps, and L < n. Total for both phases is still O(n).

Midpoint — Time: O(n), Space: O(1). fast traverses the list once at double speed, so the loop runs n/2 times.

Reorder List — Time: O(n), Space: O(1). Three sequential phases: split is n/2 steps, reversal is n/2 steps, interleave is n/2 steps. Sum is 3n/2, which is O(n). No allocation in any phase — every node is relinked, none created. The constant factor is worth noticing: this is three passes, and an array-based solution is one pass plus O(n) memory. The pointer version wins on space, not on speed.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Linked List Cycle II enters today. Grade the derivation, not just the code: if you produced the correct entry-finding loop but could not say why resetting to the head works, log it warm at best. The proof is the part that survives when the template is forgotten.