Fast and Slow Pointers

1The mental model (what this really is)#

Picture two runners on the same track. One jogs, one sprints, and the sprinter moves two steps for every one step the jogger takes. Ask a few questions about those runners and you basically have the whole pattern.

Straight-line track: the midpoint falls out for free.

• The sprinter reaches the end first.
• When the sprinter is at the end, the jogger is exactly halfway.
• That is the midpoint trick, and it works because the sprinter covered twice the distance in the same number of moves.

Looping track: the collision proves a cycle.

• If the end secretly connects back to somewhere earlier, the sprinter can never escape and keeps circling.
• The jogger is stuck on the same loop, just slower.
• The sprinter closes the gap by exactly one node per move, so he eventually laps the jogger and they land on the same spot.
• That collision is proof a cycle exists. This is Floyd's cycle detection (the tortoise and hare), which dates to the 1960s and has been an interview staple ever since.

The core insight.

• When two things move through the same structure at different speeds, the gap between them changes in a predictable way.
• On a straight line the gap grows. On a loop the gap shrinks by one each step until it hits zero.
• You exploit that gap: sometimes it tells you a cycle exists, sometimes where the middle is, sometimes the Nth element from the end.

Two pointers, different speeds, read the gap. That is the entire pattern.

2How to recognize it (the signals in a problem)#

You rarely get a problem that says "use fast and slow pointers." You have to smell it. These are the tells I look for.

• Linked list and you want O(1) extra space. The second someone says "don't use a hash set" or "constant space," your hash-set instinct is dead and this pattern should light up. The hash-set solution is O(n) space, this one is O(1), and that gap is the whole point of the follow-up.
• The word "cycle" appears. Detect a cycle, find where it starts, measure its length. All Floyd.
• You need the middle of a list in one pass. You cannot index into a linked list, and the two-pass fix (walk once for length n, walk n/2 again) touches nodes twice. Fast and slow finds the middle in a single traversal.
• "Nth from the end." One pointer gets an N-step head start, then both move together. When the leader hits the end, the follower sits exactly N nodes back, on the answer.
• A sequence where each value points to a next index and you are asked if it loops. Think "keep squaring digits" or "jump by array value." That hidden chain is a linked list in disguise, and a disguised linked list means Floyd works.

3The template (how it works, with pseudocode)#

Here is the cycle-detection skeleton. Memorize this shape. Everything else is a variation on it.

function hasCycle(head):
    slow = head
    fast = head

    while fast is not null and fast.next is not null:
        slow = slow.next          # move 1 step
        fast = fast.next.next     # move 2 steps
        if slow == fast:          # they met -> cycle
            return true

    return false                  # fast fell off the end -> no cycle

Two things people get wrong here, and both cost you.

• The loop condition is fast != null AND fast.next != null. You check fast.next because the very next line calls fast.next.next. Skip it and you throw a null-pointer exception on an even-length list, because fast lands on the last node and fast.next is null.
• Order matters. Test fast != null first, since the second clause dereferences fast.
• Compare after moving, not before. Start both at head and compare first and they are trivially equal, so you falsely report a cycle on step zero.

The middle variant is the same shape, minus the equality check.

function middle(head):
    slow = head
    fast = head
    while fast is not null and fast.next is not null:
        slow = slow.next
        fast = fast.next.next
    return slow                   # slow is at the midpoint

• For a list of length 6, this returns node 4 (the second of the two middles).
• Starting fast = head.next instead returns node 3, the first middle.
• Pick your convention before you write a line.

4A worked example (walk through one problem step by step)#

Let's do the hardest of the easy ones: not just "is there a cycle" but where does the cycle start? This is Linked List Cycle II, a Medium that shows up far more than its rating suggests, and it separates people who memorized the template from people who understand it.

The list is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 3, where node 6 points back to node 3. So the tail 3,4,5,6 is a loop and node 3 is where the loop begins.

Phase 1: find a meeting point.

Run the standard template. Slow moves one, fast moves two.

• Start: slow=1, fast=1
• Step: slow=2, fast=3
• Step: slow=3, fast=5
• Step: slow=4, fast=3 (fast went 5 -> 6 -> 3)
• Step: slow=5, fast=5

They meet at node 5 after four moves. We know there is a cycle, but node 5 is not the loop start. The start is node 3, so we are not done.

Phase 2: find the start.

Reset one pointer to the head, leave the other at the meeting point, then move both one step at a time at the same speed. Where they meet is the loop start.

• slow=1 (reset to head), fast=5 (stays at meeting point)
• Step: slow=2, fast=6
• Step: slow=3, fast=3

They meet at node 3 after two moves. That is the answer.

Why this works (the one-sentence intuition).

• Call the distance from head to the loop start a (here a=2, node 1 to node 3).
• Call the distance from the loop start to the meeting point b (here b=2, node 3 to node 5).
• When they met, slow had walked a + b, and fast walked exactly twice that, so the extra distance fast covered is a whole number of loop laps.
• Work that out and a equals the distance from the meeting point back around to the loop start.
• So a pointer from head and a pointer from the meeting point, both moving one step, cover a at the same moment and collide right at the entrance.

The takeaway: phase one proves a cycle and gives a meeting point, phase two converts that meeting point into the loop entrance with a head reset and an equal-speed walk.

5Variations and gotchas#

The template barely changes across these. What changes is where you start the pointers and what you do when the walk ends.

• Middle of a list. One pointer double-speed, return slow at the end. For even length, decide up front whether you want the first or second middle. Starting fast at head versus head.next shifts which one you land on, and interviewers do ask "which middle?"
• Nth node from the end. This is a fixed-gap two-pointer, not a speed difference. Advance one pointer N steps first, then move both at the same speed. When the leader hits null, the follower is on the Nth-from-end. To remove it, stop the follower one node early and use a dummy node before head so you can delete the very first node cleanly.
• Palindrome linked list. Find the middle with fast and slow, reverse the second half in place, then compare halves node by node. Clean O(1) space. It is a favorite because it chains two patterns, and it is where most people fumble the pointer reversal under pressure.
• Happy number and implicit chains. No real list exists. The "next" is sum of squares of digits. Run slow and fast over that function. Meet at 1 means happy, meet anywhere else means a cycle that never reaches 1. Same template, the pointer is just an integer and .next is a function call.
• Cycle length. Once slow and fast meet, keep one still and walk the other around until it returns, counting steps. That count is the loop length. In the section 4 example it would be 4, the nodes 3,4,5,6.

6Complexity#

Time is O(n).

• The slow pointer visits each node at most a constant number of times.
• In cycle detection, once both pointers are inside the loop, fast closes the gap by one node per step and catches slow within one loop traversal.
• Total work is at most about 2n pointer moves, still linear even though fast moves twice as fast.

Space is O(1), and that is the entire selling point.

• The naive alternative stores every visited node in a hash set and checks for repeats.
• That is also O(n) time but costs O(n) space.
• When an interviewer pushes you from the hash-set answer to "can you do better on space," fast and slow is the better they want.

7Mistakes that cost people the round#

• Null-check sloppiness. Not guarding fast.next before fast.next.next. Throws on even-length and empty lists. The most common crash on this pattern.
• Comparing before moving. Returns a false-positive cycle on step zero. Move first, then compare.
• Forgetting phase two exists. Candidates find the meeting point and declare victory when the question asked for the loop start. Read the prompt. Meeting point and loop start are different nodes, node 5 versus node 3 in our example.
• Jumping to the answer with no reasoning. Interviewers have seen the template a thousand times. Say why the two speeds collide (the gap shrinks by one each step inside the loop) or why the head reset finds the entrance (a equals meeting-point-to-start). That one sentence gets you the hire.
• Not handling a single node or empty list. head is null, or head.next is null. State these two cases out loud before you code. It takes five seconds and signals care.
• Reaching for a hash set when they explicitly banned extra space. You would be shocked how often panic wins and someone grabs the set anyway.

8Your practice path (named problems by difficulty)#

Do them in this order. Do not skip the easy ones, they build the muscle memory that makes the hard ones feel routine. Target roughly 25 to 30 minutes each, and re-solve any one you needed a hint on a day later from scratch.

Warm up (Easy):

• Linked List Cycle (the bare hasCycle template)
• Middle of the Linked List (midpoint, pick your convention)
• Happy Number (first implicit-chain problem)
• Palindrome Linked List (middle plus reverse-in-place)

Core (Medium):

• Linked List Cycle II (find the start, the one from section 4)
• Remove Nth Node From End of List (fixed-gap, use a dummy head)
• Find the Duplicate Number (the sneaky array-as-linked-list version)
• Reorder List (middle, reverse, then merge two halves)
• Sort List (uses the middle-finding step to split for merge sort)

Stretch (Hard-ish):

• Rotate List (fixed-gap thinking plus wraparound)
• Circular Array Loop (implicit chain with direction and self-loop edge cases)

When you can do Find the Duplicate Number and explain why an array of numbers is secretly a linked list, you own this pattern. That one is the litmus test, everything else is a warm-up for it.

9Where this shows up#

• A staple of phone screens and the first onsite coding round almost everywhere.
• A rite of passage at the big product companies, and constant at fast-moving startups that pull from the classic question bank.
• Expect at least one linked-list or cycle question in any round that lists "data structures" on the rubric.
• Low-risk, high-signal for them: cheap to pose, solvable in 20 minutes, and it cleanly separates people who understand pointer mechanics from people who only memorized sorting.
• Linked List Cycle and its "find the start" sequel, plus Find the Duplicate Number, are among the most-repeated single-topic questions in the whole screening bank.

Want to know which companies lean on linked-list and pointer questions in which rounds? Check the company guides to see where this pattern tends to appear.