When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Linked structure
- Cycle detection
- Middle element
When another approach fits better
- Random access makes direct indexing simpler
- Node identity is unavailable or the process does not advance deterministically
How it works#
Store every visited node/state in a set, or count length in one pass and locate the target in another.
Choose the relative movement that represents the desired distance.
Write safe dereference conditions before movement.
For cycles, use relative-speed reasoning; for nth-from-end, establish the gap before moving together.
InvariantThe pointer separation or relative speed encodes the property; pointer equality means identity, not equal stored values.
Example and template#
Linked List Cycle
Reason about node identity and relative pointer speed.
Open the full problem brief- Start
S,F → 1 → 2 → 3 ↘Both begin at the same node.
- Inside cycle
S advances 1; F advances 2Relative distance changes by one, so they meet if a cycle exists.
slow = start
fast = start
while fast exists and fast.next exists:
slow = slow.next
fast = fast.next.next
if slow is fast: cycle exists- Time
- O(n)
- Space
- O(1) extra
- Assumptions
- Traversal follows a deterministic next relation and equality compares node/state identity.
Pitfalls#
Common wrong approaches
Repeated values can create a false meeting; the proof requires identical nodes.
Checking only fast misses a null fast.next dereference.
Edge cases
- Empty list
- One node with or without self-cycle
- Even versus odd length
- Requested gap exceeds length
Interview narration
- “I need a relationship between positions, not stored values.”
- “The faster pointer either reaches null or laps the slower pointer inside a cycle.”
- “My loop guard makes both fast dereferences safe.”
Practice#
Linked List Cycle
Reason about node identity and relative pointer speed.
Practice this problemRemove the kth node from the end in one traversal.
Reveal the pattern decision
Create a k-node lead, then advance both pointers so the follower stops at the predecessor.
Transfer problem
Detect whether a deterministic state-transition function eventually repeats without retaining all states.
Checkpoint: Define state identity and termination before applying cycle detection.
Follow-up variations
- Find the cycle entry
- Handle the midpoint convention for even-length lists
Error-log prompts
- Did equality mean identity?
- Were both fast-pointer dereferences guarded?