Linked Lists II — Cycles, Middle, Reorder

Review boundary and corrected contracts

Cycle detection compares node identity. Middle, reorder, and palindrome operations assume an acyclic list. This reorder implementation splits at the first middle and severs the link before reversing; otherwise interleaving can create a cycle. Empty/single-node lists are valid no-ops; testing must check identities and absence of new cycles.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Own slow-fast pointers for cycle detection, entry-point location and midpoint finding, then compose them with reversal to solve Reorder List and Palindrome Linked List in O(1) space.

Series: LeetCode — From Basics to Production-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 structured practice: 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.

Let t be slow’s total number of steps at the first post-move meeting. Its distance is t = L + m + qC for some q ≥ 0, allowing completed laps. Fast has travelled 2t, and their distance difference t is a positive multiple of C. Consequently L + m ≡ 0 (mod C), or L = kC − m for an integer k ≥ 0.

Starting at the head and walking L steps reaches the entry. Starting at the meeting point and walking L steps reaches offset m + L ≡ 0 (mod C), the same entry. Before L steps, the head-walker is outside the cycle, so the pointers cannot meet sooner. When L = 0, both already start this phase at the entry; k can be zero. A self-loop illustrates why assuming no completed lap at detection is unsafe.

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. The first-middle guard needs a nonempty head. We use it for a balanced split: the second half is no longer than the first. A second-middle split is not automatically wrong for reorder; with second = slow.next, severing, and the same interleave loop, an even-length list leaves two central nodes already in their final order. For palindrome comparison, use the balanced split so all mirrored pairs are checked.

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 an acyclic list to an array of nodes simplifies indexing, but still requires careful relinking and O(n) storage. 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. Using only while fast can fail on odd lengths when fast.next is None; using only while fast.next can fail after fast becomes None on even lengths (and on an empty list).

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.

Two implementation details that break this quietly. First, compare with is, not ==. Node objects may define __eq__ by value, and two distinct nodes holding the same value would then compare equal and report a spurious cycle. Identity is what you mean. Second, the entry-finding loop must start from head, not from where slow was before the meeting — the algebra L = kC - m is specifically about the distance from the head, and any other starting point invalidates 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.

Palindrome solution with restoration. Save the reversed half’s head even if comparison fails; do not return early before putting it back. The odd middle is deliberately outside the shorter second half.

def is_palindrome(head):
    if head is None or head.next is None:
        return True
    slow = fast = head
    while fast.next and fast.next.next:
        slow, fast = slow.next, fast.next.next
 
    def reverse(node):
        prev = None
        while node:
            nxt = node.next
            node.next = prev
            prev, node = node, nxt
        return prev
 
    second = slow.next
    slow.next = None
    reversed_head = reverse(second)
    first, second = head, reversed_head
    same = True
    while second:
        if first.val != second.val:
            same = False
        first, second = first.next, second.next
    slow.next = reverse(reversed_head)
    return same

For [1,2,3,2,1], compare [1,2] with the reversed second half [1,2], skip the middle 3, then restore every original next link. For [1,2,3,1], the second comparison fails, but restoration still runs. Time is O(n), auxiliary space O(1), assuming value comparison does not raise an exception.

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.

Mixing split conventions. The first-middle split gives halves of equal length or a one-node excess on the left. The second-middle split after slow also works for this reorder loop: on [1,2,3,4], split [1,2,3] | [4] and interleave to [1,4,2,3]. Do not call it a bug merely because the midpoint differs. But for palindrome comparison it misses a pair: [1,2,3,1] would compare only the outer 1s.

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.

Myth: Detecting a cycle is the hard part; once you know one exists, finding the entry point requires walking the cycle to measure its length and then doing a second pass with a gap.

Why: Detection is the easy half — two pointers at different speeds must eventually coincide inside any cycle, and that takes four lines. Finding the entry is the part with actual content, and it needs no length measurement at all: the algebra L = kC - m falls out of the fact that fast travelled exactly twice slow's distance, and it says that walking L steps from the head and L steps from the meeting point land on the same node. Reset one pointer to the head, step both by one, done. Measuring C first works but is strictly more code for the same result.

Steps 1: Because fast advances two nodes per step and slow advances one, the gap between them grows by exactly one per step and can never skip a value.

Steps 2: Because a cycle is finite and both pointers are eventually inside it, a gap that grows by one modulo the cycle length must hit zero — so they always meet if a cycle exists, and fast reaches the end if it does not.

Steps 3: At the meeting, slow has travelled t = L + m + qC and fast has travelled 2t. Their difference t is a multiple of C, so L + m ≡ 0 (mod C), including L = m = 0.

Steps 4: Because walking L steps from the meeting point covers kC - m from a position m past the entry, it lands on a whole number of laps and therefore back at the entry — the same node the head-walker reaches after L steps.

Steps 5: Because the same slow-fast machinery on an acyclic list leaves slow at half of fast's distance when fast reaches the end, the midpoint is a free by-product of the identical loop.

Steps 6: Testable prediction: on 1->2->3->4->5->6->3, the pointers meet at node 5 and the entry loop then takes exactly two steps to reach node 3. If your meeting point differs, the guard or the step counts are wrong.

Picture: Two runners on a track, one at double pace. On a straight road the fast one simply finishes and leaves. On a loop the fast one laps the slow one, and lapping means they stand on the same spot — no cycle can hide from that.

Trigger: Fires on 'cycle', 'loop', 'middle node', 'second half', and on any O(1)-space requirement over a structure you cannot index into.

Name: Floyd's tortoise and hare

Gain: O(1) space, single pass for detection, and the entry point comes out with four extra lines and no length measurement.

Cost: The correctness argument is non-obvious and easy to misstate; the loop guard has two required halves; identity-versus-equality is a silent trap.

Name: Hash set of visited nodes

Gain: Five lines, obviously correct, returns the entry node directly as the first repeat, and needs no proof to defend.

Cost: O(n) space, which fails the stated constraint on every version of this problem that bothers to state one.

Name: Copy nodes to an array, then index

Gain: Turns midpoint, palindrome and reorder into trivial index arithmetic with no pointer surgery at all.

Cost: O(n) space, and it dodges the exact skill the question is probing. Fine as a stated fallback, weak as a final answer.

Pick: Use Floyd whenever the problem states O(1) space — which for cycle and reorder problems is nearly always. Use the hash set when no space constraint is given AND you are short on time, but say explicitly that you are trading O(n) space for implementation speed.

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. These are three sequential O(n) phases, not exactly 3n/2 pointer operations. An array solution also traverses and relinks the nodes; neither implementation has a measured speed guarantee here. The established advantage is O(1) auxiliary space.

Self-check (answer follows each question).

Q: Why must the loop guard be while fast and fast.next rather than just while fast?

A: The body dereferences fast.next.next. If fast.next is None, that is a null dereference. Both conditions are required, and short-circuit evaluation order is what makes the guard safe.

Q: State the identity that lets you find the cycle entry, and what each term means.

A: L + m ≡ 0 (mod C), equivalently L = kC − m for an integer k ≥ 0. L is head-to-entry distance, C is cycle length, and m is the meeting offset. Slow’s distance is t = L + m + qC, and the meeting implies t ≡ 0 (mod C). When the entry is the head, L = m = k = 0 is allowed.

Q: Why must the entry-finding loop restart from the head specifically?

A: The identity is a statement about the distance from the head. Walking L steps from the head reaches the entry by definition; walking L steps from the meeting point covers kC - m from a point m past the entry, landing on a whole number of laps and therefore also at the entry. Any other starting point breaks the algebra.

Q: Why compare nodes with is rather than ==?

A: Node classes may define value-based equality, so two distinct nodes holding the same value would compare equal and report a cycle that does not exist. The algorithm is about the pointers being the same object.

Q: In Reorder List, what breaks if you omit slow.next = None?

A: The two halves stay connected, so after reversing the second half the interleave phase creates a cycle. The symptom is an infinite loop or memory blowup rather than a wrong answer, which makes it harder to diagnose.

Q: Find the Duplicate Number gives an array of n+1 integers in the range [1, n] with exactly one duplicate, and forbids modifying the array or using extra space. How does Floyd apply?

A: Treat index i as a node with an edge to index nums[i]. Since all values lie in [1, n] and there are n+1 slots, the functional graph starting from index 0 must contain a cycle, and the cycle's entry point is the duplicated value — because entry has distinct incoming edges from the tail of the path out of index 0 and from inside the cycle. Index 0 has no incoming edge since every value is at least 1, so it is not itself on the cycle. Only the duplicated value can have more than one predecessor; it may have more than two when repeated several times. Run standard Floyd over the mapping i -> nums[i] and return the entry node's index.

Stretch: true

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.

• One mechanism — two pointers at different speeds — answers three questions: is there a cycle, where does it start, and where is the middle.

• The guard is while fast and fast.next, both halves required, because the body dereferences fast.next.next.

• Cycle entry needs no length measurement: L = kC - m means resetting one pointer to the head and stepping both by one lands them both on the entry.

• Compare nodes with is, never == — value equality reports phantom cycles.

• Reorder List is split + reverse + merge. Three primitives you already own, composed. Sever the halves with slow.next = None or you build a cycle.

• Choose your midpoint deliberately: while fast and fast.next gives the second middle on even lengths, while fast.next and fast.next.next gives the first.

Corrective source notes

• Names and objects — Python 3.14 documentation — Multiple names can refer to the same object, so mutations and copied references must be distinguished. Checked 2026-10-07.

• Names and objects (CPython v3.14.0) — aliasing and mutations, freshly checked against tagged source on 2026-10-09.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.