Pointer Techniques

What is this?

Two runners set off around a track, one at twice the speed of the other. If the track is a straight line, the fast runner finishes and the question is over. If it loops, the fast runner must eventually lap the slow one — they meet, and the meeting itself proves the loop exists. No map of the track, no marking the ground, no memory of where you have been.

That is the first half of this chapter. The second half is a different kind of cleverness: when you need to remember a mapping from every old node to its copy, and are not allowed a hash map, you can build the mapping into the list itself.

💡 Fun fact: why does resetting one pointer to the head find the loop's entrance? Let a be the distance from head to entry and b the distance from entry to the meeting point. When they meet, the slow pointer has walked a + b and the fast one exactly twice that — so the extra distance the fast pointer covered is a whole number of loops. That forces a to equal the remaining distance from the meeting point back around to the entry. Two pointers stepping one at a time from the head and from the meeting point therefore arrive together, at the entry.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: with one successor per node and no spare memory, you buy global knowledge either by running two pointers at different rates or by temporarily rewriting the structure so the information you need becomes locally reachable — then restoring it.

1. Two speeds

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow is fast:
        return True          # they can only meet inside a loop
return False                 # fast fell off the end

The loop condition is the part to get right: fast and fast.next, because the fast pointer takes two steps and either could walk off the end. Checking only fast crashes on even-length lists.

The same skeleton, retuned, gives you the middle node (when fast reaches the end, slow is halfway) and the k-th from the end (start fast k nodes ahead, then advance both until fast hits the end). One pass each, no length precomputation.

2. Interleave instead of mapping

To deep-copy a list whose nodes carry an arbitrary random pointer, the obvious solution maps each original node to its copy — O(n) space. The trick removes the map by making each copy findable from its source:

pass 1 — weave:      A → A' → B → B' → C → C'
pass 2 — randoms:    A'.random = A.random.next     ← the copy of whatever A pointed at
pass 3 — unweave:    A → B → C   and   A' → B' → C'

Pass 2 is the whole idea: because every copy sits immediately behind its original, "the copy of node X" is always X.next. The map is not gone — it is encoded in the list's own shape.

Pass 3 must restore the original list exactly. Leaving it interleaved is a correctness failure, not a tidiness one: the caller still holds a reference to it.

3. A 30-second worked example (finding the loop entry)

1 → 2 → 3 → 4 → 5
        ↑       |
        └───────┘        entry is node 3, loop length 3

step  slow  fast
 1     2     3
 2     3     5
 3     4     4      ← meet at node 4

reset one pointer to head, advance both by one:
       1     4
       2     5
       3     3      ← meet at node 3, the entry ✓

Distance head→entry is 2, and distance meeting-point→entry going forward around the loop is also 2. That equality is exactly what the fun-fact argument above proves.

4. Where you'll actually meet this

• Dependency and build systems. Detecting import cycles or circular module dependencies, where the graph is walked rather than stored.
• Pseudo-random generators. Finding a generator's period is cycle detection on the sequence it produces — Floyd's original motivation, and still how PRNG quality is measured.
• Pollard's rho factorisation. The same tortoise-and-hare, applied to a numeric sequence, is a practical integer-factorisation method.
• Filesystem traversal. Symlink loops must be detected without holding every visited inode in memory on constrained systems.
• Serialisation and ORMs. Deep-copying an object graph with arbitrary cross-references is Copy List with Random Pointer at production scale — usually with a map, but the constraint version teaches why the map was needed.

5. Problems in this chapter

▶ Linked List Cycle

Determine whether a list contains a loop, in O(1) space. Floyd's tortoise and hare, and the follow-up — where does the loop start — is where the interesting conversation begins.
Pattern: two speeds. Target: O(n) time, O(1) space (versus the O(n)-space hash-set baseline).

▶ Copy List with Random Pointer

Deep-copy a list where each node also points at an arbitrary node. Weave the copies in, resolve the random pointers locally, then unweave.
Pattern: restructure-then-restore. Target: O(n) time, O(1) extra space (versus the O(n)-space map).

6. Common pitfalls 🚫

• Checking only fast in the loop guard. You need fast and fast.next — the two-step advance can fall off either node.
• Starting the pointers one apart "to avoid the immediate match". Start both at the head and advance before comparing; offsetting them makes the entry-point proof stop working.
• Forgetting to unweave. The original list must be returned to its exact prior shape, since the caller still references it.
• Handling random = None carelessly. node.random.next dereferences null when random is unset; guard it explicitly.
• Assuming the loop starts at the head. The meeting point is not the entry, and the entry is rarely the head — the reset step is required.
• Reaching for a hash set and stopping there. It is a correct O(n)-space answer and the right thing to say first, but the follow-up is always "now do it in O(1)".

7. Key takeaways

1. Two pointers at different speeds reveal structure neither could see alone — cycle existence, the middle, the k-th from the end.
2. Meeting proves a loop; a reset finds its entry. Know the argument, not just the steps.
3. Guard both fast and fast.next.
4. Restructuring can replace a hash map. Interleaving makes "the copy of X" reachable as X.next.
5. Restore what you rearranged. A temporarily broken input must be intact when you return.
6. Why interviewers like it: the code is ten lines, so the entire signal is in your edge-case handling and whether you can explain why the pointers meet where they do.

Order: Linked List Cycle → Copy List with Random Pointer.