Two Pointers II — Same Direction & Fast-Slow

Review boundary and corrected contracts

Floyd stores two node references, not two integer values. Inside a cycle the relative position advances modulo the cycle length; a reset probe meets the slow pointer at the entry. A linked list must allow repeated successor access; a one-pass event stream is a different contract.

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 the same-direction pointer family: read/write compaction, the merge-from-the-back trick, and Floyd's tortoise and hare with the cycle-entry proof.

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

Prerequisites. L07 (Two Pointers I — opposite ends) helps but is not required. You need only: what a Python list is, what indexing costs (O(1)), and the definition of a singly linked list node (a value plus a next pointer). Everything else is built here from scratch.

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 inputs, with spare capacity at the end of the first list. Fill that first list backward so unread values in its prefix survive. The second input remains separate.
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 node references. The naive alternative for compaction is building a fresh list — O(n) memory — instead of rewriting in place.

The running track

Real: On a circular track, the faster runner eventually catches the slower runner again. On a finite straight track, it reaches the end. Compare positions only after advancing; their initial shared start is not evidence of a cycle.

fast = fast.next.next; slow = slow.next — if fast ever equals slow, the list loops; if fast falls off the end, it doesn't.

First principles

Detection proof. Assume a finite, stable successor structure using ordinary ListNode objects, which are truthy and compare by identity. A node has one next reference, and no other code mutates it during traversal. An acyclic chain ends in None, so the guarded fast pointer reaches the end. Equal stored values do not imply repeated nodes.

If the reachable structure has a cycle of length L, both pointers are eventually in it. After t rounds their cycle positions differ by t modulo L, since their total traveled distances are t and 2t. Each new round changes the relative position by one modulo L; within at most L further rounds it is zero. This is modular progress, not a nonnegative gap decreasing forever without wraparound. Starting at the same head and checking only after moving gives a real subsequent meeting. With tail length a, detection takes O(a+L) successor operations and O(1) node references. The first meeting need not be the entry.

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

At the start of iteration read, the prefix [0, write) contains the retained values from original [0, read), in order; write <= read. Thus read-write counts discarded values in the already processed prefix, not at every point inside the loop. After processing the current value, the corresponding count is read+1-write. The physical length is unchanged and the suffix is unspecified. The predicate must not mutate the list; evaluating a slice for display would allocate a copy.

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 the reset works. Let a be the tail length, L the cycle length, b the meeting node’s offset from the entry (0 <= b < L), and t the number of rounds at the first post-move meeting. Slow may have completed extra laps: t = a+b+qL for some nonnegative q. Fast traveled 2t; meeting at the same cycle position implies their difference t is a multiple of L. Therefore a+b ≡ 0 (mod L). After a further steps, a probe starting at head reaches the entry, while the probe starting at the meeting point has cycle offset (b+a) mod L = 0. Before those a steps, the head probe is outside the cycle, so they cannot meet sooner. If a=0, the meeting offset is already zero and the reset loop takes zero steps. This proof includes arbitrary tail lengths and extra laps; it does not assume slow traveled only a+b.

Template D — merge backward into reserved space

nums1 contains m valid sorted values followed by n spare slots; its total length is m+n. nums2 is a separate non-aliasing sorted list of length n. Counts are nonnegative, inputs contain bounded integers, and mutation of nums1 is permitted. Spare values are placeholders, not part of its sorted input.

def merge_back(nums1, m, nums2, n):
    i, j, write = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[write] = nums1[i]
            i -= 1
        else:
            nums1[write] = nums2[j]
            j -= 1
        write -= 1
    return nums1

The suffix beyond write is already the correctly merged greatest values. The greatest remaining value is at one of the two input ends. While j>=0, write=i+j+1 > i, so writing nums1 never overwrites an unread value in its valid prefix. When nums2 is exhausted, nums1’s remaining prefix is already in its final location; when nums1 is exhausted, the loop copies the rest of nums2. Each iteration consumes one input value: O(m+n) worst-case time, O(1) auxiliary references, unchanged nums2. This is not the harder problem of merging arbitrary adjacent runs with no spare capacity.

Mental model

Name: The gap is the payload

Picture: Attach meaning to pointer relations, but distinguish the algorithms. Compaction uses processed-count minus kept-count at loop entry; merge-back uses free slots to protect unread values; Floyd tracks relative position modulo cycle length.

• One pointer reads/explores; the other lags with a meaning attached to the lag.

• Fast-slow: advance slow by 1, fast by 2, guard fast and fast.next.

• Never overwrite what you still need to read — merge from the back, not the front.

• Entry location follows from a+b being a multiple of L, including any complete slow-pointer laps.

Trigger: 'in place, O(1) extra memory', 'detect a cycle', 'find the middle in one pass', or 'merge into the first array without extra space'.

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. Remember (a+b) mod L = 0: the tail distance and meeting offset complete a whole number of laps. From head and the meeting point, a equal-speed steps reach the entry together.

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

Myth: Floyd's meeting point is the node where the cycle starts, so you can return it directly.

Truth: The first meeting point is somewhere inside the loop, generally NOT the entry. Finding the entry needs the reset-to-head second phase.

Why: Slow enters the loop and fast is already looping; they collide wherever the closing gap first hits zero, which depends on the tail length a and loop length L — not on the entry node.

Test: For the shown initialization, build 1→2→3→4→5→3. After each round, (slow, fast) is (2,3), (3,5), (4,4): the first meeting is node 4, not node 3. Resetting one probe to node 1 gives (2,5), then (3,3), locating the entry.

What reviewers 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 · Practice selection. — 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 · Practice selection. — 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 · Practice selection. — 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 · Practice selection. — 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 · Practice selection. — probes: read/write compaction in place. Follow-up: allow each value at most twice (80).
• Move Zeroes (283) · Easy · Practice selection. — probes: compaction that also preserves order of the non-zeros. Follow-up: minimise the number of writes.

These examples compare constant auxiliary storage and repeated traversal. Floyd’s entry algorithm has two phases and revisits nodes; calling it literally one pass would be misleading even though total successor work is linear.

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. A reviewer 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 modular 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 requires repeated successor access; an irreversible one-pass event stream has a different input contract.

Goal: Return the LENGTH of the cycle (number of nodes in the loop), not the entry.

Hint: After the collision, freeze slow and walk a second pointer around until it returns to slow, counting steps.

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) auxiliary memory. For at most two copies, either keep the first min(2,n) elements and scan from index 2, or use the guarded form below. It handles empty and singleton lists without returning an impossible length:

def remove_duplicates_twice(nums):
    write = 0
    for x in nums:
        if write < 2 or x != nums[write - 2]:
            nums[write] = x
            write += 1
    return write

3. Middle of the Linked List (876)

Plain words: for a finite acyclic list, return its middle node, choosing the second middle for even length. Empty input returns None. Running this middle finder on a cycle would not terminate; use the cycle contract separately.

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) auxiliary memory. For the first middle with empty input still supported, use while fast and fast.next and fast.next.next; otherwise an initial None would be dereferenced. After r rounds slow is at index r and fast at 2r, which explains the different even-length stopping points.

4. Move Zeroes (283) — compact, then fill the suffix

Plain words: mutate the caller's list of bounded integers so that every nonzero value stays in its original relative order and every zero ends up after them. Keep the same list object and its full original length; return None. Empty input stays empty. This is not Remove Duplicates' logical-prefix contract: every slot of the resulting list matters.

A reference answer can collect the nonzeros into a new list and append the original number of zeros, but that uses O(n) extra storage. In place, first do stable read/write compaction with x != 0. Only after the entire input has been read, fill every slot from write through len(nums)-1 with zero. Merely calling compact and returning its length leaves old values in the suffix; deleting that suffix would incorrectly shorten the array.

def moveZeroes(nums):
    """Mutate the same full-length list; preserve nonzero order; return None."""
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write] = nums[read]
            write += 1
    # All original values have now been examined: the unread region is empty.
    for index in range(write, len(nums)):
        nums[index] = 0

Why both phases are necessary. At each scan-loop entry, [0, write) contains exactly the nonzeros of original [0, read), in their original order, and write <= read. A copy therefore cannot overwrite a future unread value. At scan completion, write is the total nonzero count. The remaining n-write positions must be zeros, because that is precisely the original zero count. Filling those positions now cannot destroy unread input or disturb the retained prefix. Together these facts prove the full-array postcondition, not just the prefix postcondition. The function assigns existing slots only: it neither resizes nor rebinds the caller's list, so aliases see the mutation.

For [0, 1, 0, 3, 12], compaction gives write=3 and the temporary list [1, 3, 12, 3, 12]. Zero-filling indices 3 and 4 produces [1, 3, 12, 0, 0]. [0, 0] stays two zeros, [2, -1] is unchanged, and [] executes neither loop. A second call leaves the result unchanged.

Complexity: O(n) time and O(1) auxiliary storage under bounded-integer costs. There are n scan iterations, at most n compaction writes and at most n suffix writes (together exactly n assignments in this version). It does not minimize writes: already-correct slots can be assigned to themselves. For that optional follow-up, skip the compaction assignment when write == read and skip a suffix assignment if the slot is already zero; keep the same invariants.

Self-test the contract, not just a returned prefix: with nums = [0, 1, 0, 3, 12] and alias = nums, moveZeroes(nums) must return None, alias is nums must remain true, len(nums) must remain 5, and both names must show [1, 3, 12, 0, 0]. For a bounded independent oracle, enumerate short lists over [-1, 0, 1] and compare the entire result with a freshly collected nonzero list followed by the original zero count. Also test empty, all-zero, no-zero and repeated-nonzero inputs. The oracle may allocate; the in-place solution may not.

Tradeoff

Decision: Detect a cycle in a linked list.

Name: Visited set

Gain: Dead simple; also gives you the entry node for free (first revisit).

Cost: O(n) extra memory; hashing overhead per node.

Pick: Extra storage is acceptable and nodes are hashable by identity. If nodes define value equality or are unhashable, a plain set of those nodes does not implement identity visitation; use a suitable identity-keyed representation while keeping nodes alive.

Name: Floyd's fast-slow

Gain: O(1) auxiliary node references without requiring nodes to be hashable.

Cost: Two-phase logic for the entry; the proof is non-obvious under pressure.

Pick: When O(1) space is required, or a reviewer asks for the entry with justification.

Name: Destructive marking

Gain: O(1) space by mutating nodes (e.g. point next to a sentinel).

Cost: Destroys the list; unacceptable if the caller needs it intact.

Pick: Almost never in practice — mentioned only to be rejected.

Verdict: Choose using memory, identity semantics, repeatable successor access and the needed output. Neither approach is an evidence-backed universal hiring requirement.

Where this shows up

Floyd-style pair scheduling can be used inside Pollard’s rho factorization, but factor detection additionally computes a gcd of iterate differences with the composite modulus; it is not just equality of the iterates modulo that modulus. Other rho variants use Brent-style scheduling.

For a small arithmetic illustration, use N=91 and f(x)=(x²+1) mod 91, starting both iterates at 2. One slow step gives 5; two fast steps give 26. The gcd of 26−5 and 91 is 7, a nontrivial factor, even though 5 and 26 are unequal modulo 91. Other seeds can fail or yield the whole N; this witness is not a general performance or success guarantee.

Read/write compaction is also a useful model for stable filtering in a fixed buffer: retain values in a prefix and expose its logical length. Real memory managers add reachability, relocation and concurrency concerns beyond this array exercise.

Checkpoint

You can now…

• Write the read/write compaction skeleton from a blank file and state its invariant.

• Write Floyd's detection with the correct fast and fast.next guard.

• Explain why fast and slow must collide iff a cycle exists.

• Derive the reset from t=a+b+qL and t≡0 mod L, allowing extra slow-pointer laps.

• Find the middle of a list in one pass and control the even-length tie.

• Solve remove-duplicates and move-zeroes in place with O(1) memory.

• Pick between a visited set and Floyd's based on the memory constraint.

Quiz

Self-check (answer follows each question).

Recall check

Q: In Floyd's, why is the loop guard while fast and fast.next and not just while fast?

A: Because you dereference fast.next.next, so both fast and fast.next must be non-None; on even-length lists fast can become None, on odd-length fast.next can become None.

Q: After the first collision, where do the two pointers meet in phase 2, and at what speeds?

A: At the cycle entry, both moving 1 step at a time — one from head, one from the meeting point.

Q: At the start of a compaction iteration, what does read − write count?

A: Discards in the original prefix of length read. After processing the current element the count is read+1-write; the timing of the invariant matters.

Q: For Middle of the Linked List with even length, what determines whether you get the first or second middle?

A: On a finite acyclic list, while fast and fast.next gives the second; while fast and fast.next and fast.next.next gives the first and also handles None safely.

Q: Why does the visited-set approach also hand you the cycle entry for free?

A: The first node you encounter that's already in the set is precisely the entry — the point where the tail rejoins the loop.

Q: ★ Stretch: what are a, L and b in the modular entry proof, and why do equal-speed probes meet at the entry?

A: a is tail length, L cycle length and b the meeting offset. After t rounds, slow traveled t=a+b+qL; fast traveled 2t. Their equal cycle position implies t is a multiple of L, hence a+b≡0 mod L. The head probe reaches the entry after a steps; the cycle probe’s offset then is (b+a) mod L=0. Before that the head probe is outside the cycle, so no earlier meeting is possible.

Stretch: true

Practice queue

Use these practice choices with actual due dates. +7d / +21d are optional elapsed-day reminders, not research-derived guarantees.

• 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!).

Corrective source notes

• 5. Data Structures — Python 3.14.8 documentation — list.copy returns a shallow copy; nested mutable elements may remain shared. Checked 2026-10-07.

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

• CP-Algorithms factorization implementations — a secondary implementation reference showing gcd-based Floyd scheduling and an alternative Brent variant; checked 2026-10-09. The N=91 witness is independently computed above.

These citations support the named claims, not blanket certification of the lesson. The Floyd/reset and merge proofs are derived explicitly; execution scope and finite-test limits are recorded separately.