L08 · Two Pointers II — Same Direction & Fast-Slow

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

Watch first

What this pattern IS

In L07 the two pointers started at opposite ends and walked toward each other. Today both pointers move the same direction, but at different rates. The useful object is no longer where each pointer is — it's the gap between them.

There are three shapes of that idea, and they all look unrelated until you notice they share one structure.

1. Read / write compaction. A read pointer scans every element. A write pointer only advances when it keeps something. The gap between them is the number of elements you have discarded. This is how you delete-in-place in O(1) extra memory.
2. Merge from the back. Two sorted regions in one array, filled from the highest index downward, so you never overwrite data you still need to read. The gap is the free space.
3. Fast / slow (Floyd's). One pointer moves one step, the other moves two. On a cycle the fast one closes the gap by exactly one node per step, so it must eventually collide with the slow one. This detects a loop in O(1) memory.

The naive alternative for cycle detection is a set of visited nodes: walk the list, and if you ever see a node you've stored, there's a cycle. That works but costs O(n) memory. Floyd's does the same job with two integers. The naive alternative for compaction is building a fresh list — O(n) memory — instead of rewriting in place.

First principles

The templates

Template A — read / write compaction

def compact(nums, keep):
    """Keep only elements where keep(x) is True, in place. Returns new length.
    write = index of the next slot to fill (also = count kept so far)."""
    write = 0
    for read in range(len(nums)):      # read scans every element
        if keep(nums[read]):           # decide: keep this one?
            nums[write] = nums[read]    # copy it forward
            write += 1                  # advance the write head only on a keep
    return write                        # nums[:write] is the compacted result

The invariant: everything in nums[:write] is already-kept and in order; read has looked at everything up to itself. The gap read - write equals the number discarded so far.

Template B — fast / slow cycle detection (Floyd)

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:     # guard BOTH: fast may be None, or fast.next may be None
        slow = slow.next          # 1 step
        fast = fast.next.next     # 2 steps
        if slow is fast:          # they collided -> cycle
            return True
    return False                  # fast fell off the end -> no cycle

The while fast and fast.next guard is the whole edge-case story: you dereference fast.next.next, so both fast and fast.next must be non-None first. Miss either and you crash on an even/odd length list.

Template C — find the cycle entry

def cycle_entry(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:                # phase 1: find any meeting point
            slow2 = head
            while slow2 is not slow:     # phase 2: walk both at speed 1
                slow2 = slow2.next
                slow = slow.next
            return slow                  # they meet AT the cycle entry
    return None

Why phase 2 works: let the tail length (head to entry) be a, and let the meeting point be b nodes into the loop of length L. When they meet, slow travelled a + b; fast travelled twice that, 2(a+b), and also a + b + kL for some integer k (it did extra full loops). So a + b = kL, i.e. a = kL - b. Walking a steps from head lands exactly a into the loop from entry = kL - b, which is the same node as b steps from the meeting point continued forward. Hence resetting one pointer to head and stepping both by 1 makes them meet at the entry.

Mental model

Memory / mnemonic

Peg the fast-slow template to a physical picture: "Tortoise, Hare, then Reset."

• Tortoise = slow, one hop. Hare = fast, two hops. Say it out loud while typing slow=slow.next; fast=fast.next.next.
• The guard is a rhyme: "fast and fast-dot-next, or you'll deref a wreck." You dereference two nexts, so two things must be alive.
• Reset = phase 2. The single equation to carry is a = kL − b — write it as three letters on scratch paper: a, L, b. "Distance to entry equals loops minus lead."

For compaction the shape-of-the-code cue is: "read every step, write only on a keep." The write head is lazy; the read head is diligent.

The trap

What interviewers actually ask

The same-direction / fast-slow family shows up constantly because it tests O(1)-space discipline and, for Floyd, a real proof.

• Linked List Cycle (141) · Easy · Amazon, Meta, Microsoft — probes: can you detect a loop without a visited-set (O(1) memory)? Follow-up escalates straight to 142.
• Linked List Cycle II (142) · Medium · Amazon, Meta — probes: can you locate the cycle entry and justify the reset step algebraically? This is the real filter; many candidates memorise it and fall apart on "why".
• Middle of the Linked List (876) · Easy · Amazon, Microsoft — probes: fast-slow to find the middle in one pass. Follow-up: for even length, do you return the first or second middle, and can you control which?
• Remove Nth Node From End of List (19) · Medium · Amazon, Meta — probes: two pointers with a fixed gap of n, then advance together. Follow-up: one-pass only, and handle removing the head.
• Remove Duplicates from Sorted Array (26) · Easy · Amazon, Microsoft — probes: read/write compaction in place. Follow-up: allow each value at most twice (80).
• Move Zeroes (283) · Easy · Meta, Amazon — probes: compaction that also preserves order of the non-zeros. Follow-up: minimise the number of writes.

The universal escalation here: "do it with O(1) extra memory" and "do it in one pass." Both are answered by this family.

Worked solutions

1. Linked List Cycle II (142) — find the entry

Plain words: given a linked list that may loop back on itself, return the node where the loop begins, or None.

Brute force: store every node in a set; the first node you revisit is the entry. O(n) time, O(n) memory. The interviewer will immediately ask for O(1) memory — that's the whole point of the question.

Insight: detect the collision with Floyd, then reset one pointer to head and walk both at speed 1; they meet at the entry (the a = kL − b argument above).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:                 # collision found
            probe = head
            while probe is not slow:
                probe = probe.next
                slow = slow.next
            return probe                 # the cycle entry
    return None                          # no cycle

Complexity: O(n) time, O(1) memory. Follow-up — "what if the list is enormous and streamed?" Floyd already needs only two pointers, so it's stream-friendly as long as you can revisit nodes; a pure one-pass stream where you can't re-read would force the set approach.

def cycle_length(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            count = 1
            p = slow.next
            while p is not slow:
                p = p.next
                count += 1
            return count
    return 0

2. Remove Duplicates from Sorted Array (26)

Plain words: a sorted array; remove duplicates in place so each value appears once; return the new length. The array is sorted, so duplicates are adjacent.

Brute force: build a new list of uniques and copy back — O(n) memory. In place is expected.

Insight: read/write compaction. write marks the end of the deduped prefix; only copy nums[read] forward when it differs from the last kept value nums[write-1].

def removeDuplicates(nums):
    if not nums:
        return 0
    write = 1                            # first element is always kept
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:   # a genuinely new value
            nums[write] = nums[read]
            write += 1
    return write                         # nums[:write] holds the uniques

Complexity: O(n) time, O(1) memory. Follow-up — "allow each value at most twice" (LC80): compare against nums[write - 2] instead, and seed write = 2.

3. Middle of the Linked List (876)

Plain words: return the middle node of a linked list; for even length, return the second of the two middles.

Insight: send fast at double speed; when fast falls off the end, slow is at the middle.

def middleNode(head):
    slow = fast = head
    while fast and fast.next:     # same guard as cycle detection
        slow = slow.next
        fast = fast.next.next
    return slow                   # even length -> second middle

Complexity: O(n) time, O(1) memory. Follow-up — "return the FIRST middle on even length": change the guard to while fast.next and fast.next.next.

Tradeoff

Where this shows up

Fast-slow cycle detection is not just a puzzle. Pollard's rho algorithm for integer factorisation uses exactly Floyd's tortoise-and-hare to find cycles in a pseudo-random sequence — the same two-speed pointers over a functional graph. Read/write compaction is the core of in-place array filtering used throughout systems code (e.g. removing tombstoned entries from a buffer without allocating) and is essentially what std::remove in C++ does: it compacts kept elements to the front and returns the new logical end.

Checkpoint

Quiz

Practice queue

Grind these easy→hard. +7d / +21d mark spaced-repetition anchors.

• Remove Duplicates from Sorted Array (26) — Easy · compaction warm-up.
• Move Zeroes (283) — Easy · order-preserving compaction.
• Middle of the Linked List (876) — Easy · fast-slow intro.
• Linked List Cycle (141) — Easy · detection · +7d anchor.
• Remove Nth Node From End of List (19) — Medium · fixed-gap pointers.
• Linked List Cycle II (142) — Medium · entry proof · +21d anchor.
• Remove Duplicates from Sorted Array II (80) — Medium · at-most-twice compaction.
• Happy Number (202) — Easy/Medium · Floyd's on a number sequence (no linked list!).