Algorithms
  • Master fast-slow pointers for finding middle elements and detecting cycles
  • Understand Floyd's cycle detection and how to find cycle start
  • Apply n-gap technique to find nth node from end in one pass
  • Use pointer switching for finding list intersection efficiently

Two Pointers for Linked Lists

Linked lists are different from arrays. You can't index into them. You can't measure their length without traversing them. You can't look at both ends simultaneously without two passes.

Except with two pointers, you can.

The fast-slow pointer technique is one of those ideas that feels almost magical the first time you see it. Two pointers moving at different speeds can detect cycles, find middle elements, and solve problems that seem impossible with a single traversal.

Finding the Middle Element

Here's a problem: find the middle node of a linked list. You don't know the length.

The naive way: traverse once to count nodes, then traverse again to the middle. Two passes.

The fast-slow way: one pointer moves twice as fast as the other. When the fast one reaches the end, the slow one is at the middle. One pass.

def find_middle(head):
    if not head:
        return None
    
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next        # One step
        fast = fast.next.next   # Two steps
    
    return slow

Let's trace through 1 → 2 → 3 → 4 → 5:

Start: slow=1, fast=1

Iteration 1:
  slow moves to 2
  fast moves to 3
  
Iteration 2:
  slow moves to 3
  fast moves to 5
  
Iteration 3:
  slow moves to 4
  fast.next is None, stop
  
Wait, that's wrong. Let me trace again:

Start: slow=1, fast=1

Iteration 1:
  fast and fast.next exist (1 and 2)
  slow moves to 2
  fast moves to 3
  
Iteration 2:
  fast and fast.next exist (3 and 4)
  slow moves to 3
  fast moves to 5
  
Iteration 3:
  fast exists (5) but fast.next is None
  Loop ends
  
slow is at 3 (the middle)

For even-length lists like 1 → 2 → 3 → 4:

Start: slow=1, fast=1

Iteration 1:
  slow moves to 2
  fast moves to 3
  
Iteration 2:
  slow moves to 3
  fast would move to None
  But we check fast.next first, which is None
  Loop ends
  
slow is at 3 (second middle element)

Why does this work? Think about the relationship between their positions. When fast has moved 2n steps, slow has moved n steps. When fast reaches the end (at position length), slow is at position length/2—the middle.

Detecting Cycles (Floyd's Algorithm)

A linked list with a cycle looks like this: 1 → 2 → 3 → 4 → 5 ↺ where 5 points back to 3.

If you traverse naively, you loop forever. How do you detect this?

Floyd's cycle detection uses the same fast-slow approach. If there's a cycle, the fast pointer will eventually lap the slow pointer, like a faster runner on a circular track.

def has_cycle(head):
    if not head or not head.next:
        return False
    
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True  # They met, there's a cycle
    
    return False  # Fast reached the end, no cycle

Let's trace 1 → 2 → 3 → 4 → 5 → 3 (5 points back to 3):

Start: slow=1, fast=1

Iteration 1: slow=2, fast=3
Iteration 2: slow=3, fast=5
Iteration 3: slow=4, fast=4  (fast went 5→3→4)

slow == fast, cycle detected!

Why does fast always catch slow in a cycle? Once both pointers are inside the cycle, the gap between them closes by 1 each iteration (fast gains 1 position). Eventually, they meet.

Finding where the cycle starts is trickier. After they meet, reset slow to the head and move both at the same speed. They'll meet at the cycle's start.

def find_cycle_start(head):
    # First, detect if there's a cycle
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # No cycle
    
    # Reset slow to head, move both at same speed
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow  # Cycle start

Why does this work? Math. The distance from head to cycle start equals the distance from meeting point to cycle start (modulo cycle length). I won't derive it here, but it's a beautiful result.

Finding the Nth Node from the End

Find the 3rd node from the end without knowing the list length.

Naive approach: count the length, then go to position (length - 3). Two passes.

Two pointers: move one pointer n steps ahead, then move both together. When the first reaches the end, the second is n from the end.

def find_nth_from_end(head, n):
    fast = slow = head
    
    # Move fast n steps ahead
    for _ in range(n):
        if not fast:
            return None  # List is shorter than n
        fast = fast.next
    
    # Move both together
    while fast:
        slow = slow.next
        fast = fast.next
    
    return slow

For 1 → 2 → 3 → 4 → 5, find 2nd from end:

Setup: fast moves 2 steps ahead
  fast at 3, slow at 1

Move together:
  fast=4, slow=2
  fast=5, slow=3
  fast=None, slow=4
  
slow is at 4 (2nd from end: 4, 5)

The gap between them is constant (n nodes). When fast falls off the end, slow is n behind.

Detecting List Intersection

Two linked lists might share a common tail: 

List A: 1 → 2 ↘
              5 → 6 → 7
List B: 3 → 4 ↗

They intersect at node 5. How do you find it?

If you knew both lengths, you could align them and traverse together. But there's a clever trick that doesn't require pre-calculating lengths.

def get_intersection(headA, headB):
    if not headA or not headB:
        return None
    
    ptrA, ptrB = headA, headB
    
    while ptrA != ptrB:
        # When a pointer reaches the end, switch to the other list
        ptrA = ptrA.next if ptrA else headB
        ptrB = ptrB.next if ptrB else headA
    
    return ptrA  # Either the intersection or None

Let's trace lists of different lengths:

A: 1 → 2 → 5 → 6 → 7
B: 3 → 4 → 5 → 6 → 7

ptrA: 1, ptrB: 3
ptrA: 2, ptrB: 4
ptrA: 5, ptrB: 5  → Found!

For lists without intersection:

A: 1 → 2 → 3
B: 4 → 5

ptrA: 1, ptrB: 4
ptrA: 2, ptrB: 5
ptrA: 3, ptrB: None → switch to B
ptrA: None → switch to A, ptrB: 4
ptrA: 1, ptrB: 5
ptrA: 2, ptrB: None → switch to A
ptrA: 3, ptrB: 1
ptrA: None, ptrB: 2
ptrA: 4, ptrB: 3
ptrA: 5, ptrB: None
ptrA: None, ptrB: 4

Both None → return None (no intersection)

Why does this work? After switching, both pointers have traversed the same total distance (length of A + length of B). If there's an intersection, they'll meet there. If not, they'll both reach None.

Reversing a Linked List

This isn't exactly "two pointers" in the fast-slow sense, but it uses the same principle of tracking multiple positions.

def reverse(head):
    prev = None
    current = head
    
    while current:
        next_node = current.next  # Save next
        current.next = prev      # Reverse the link
        prev = current          # Move prev forward
        current = next_node     # Move current forward
    
    return prev  # New head

For 1 → 2 → 3 → 4:

Start: prev=None, current=1→2→3→4

Iteration 1:
  Save next=2→3→4
  1.next = None (reverse link)
  prev=1, current=2→3→4
  List state: None←1  2→3→4

Iteration 2:
  Save next=3→4
  2.next = 1 (reverse link)
  prev=2, current=3→4
  List state: None←1←2  3→4

Iteration 3:
  Save next=4
  3.next = 2 (reverse link)
  prev=3, current=4
  List state: None←1←2←3  4

Iteration 4:
  Save next=None
  4.next = 3 (reverse link)
  prev=4, current=None
  List state: None←1←2←3←4

Return prev (4), which is the new head

Checking for Palindrome

Is 1 → 2 → 3 → 2 → 1 a palindrome?

Strategy: find the middle, reverse the second half, compare both halves.

def is_palindrome(head):
    if not head or not head.next:
        return True
    
    # Find middle with fast-slow
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # Reverse second half
    second_half = reverse(slow)
    
    # Compare
    first_half = head
    while second_half:  # Second half might be shorter
        if first_half.val != second_half.val:
            return False
        first_half = first_half.next
        second_half = second_half.next
    
    return True

For 1 → 2 → 3 → 2 → 1:

Find middle:
  slow ends at 3 (middle)

Reverse second half (3 → 2 → 1 becomes 1 → 2 → 3):
  second_half points to reversed section

Compare:
  first=1, second=1 ✓
  first=2, second=2 ✓
  first=3, second=3 ✓
  second is None, stop

Palindrome!

The Pattern

Fast-slow pointers on linked lists solve:

Finding the middle: Fast moves 2x, when it reaches end, slow is at middle.

Cycle detection: If there's a cycle, fast laps slow.

Nth from end: Create n-gap, move together until first reaches end.

Intersection: Switch lists when reaching end, they'll meet at intersection (or both reach None).

These aren't tricks to memorize—they're consequences of thinking about pointer positions and relationships. Once you understand why fast-slow works for finding the middle, cycle detection becomes obvious (it's the same idea applied to a circular structure).

When Linked Lists Matter

You might wonder: why not just use arrays? Arrays are faster for most operations.

Linked lists shine when:

  • You're inserting/deleting frequently at arbitrary positions
  • You don't know the size upfront
  • You're building data structures like queues or stacks
  • You're working with memory constraints (linked lists don't need contiguous memory)

In interviews, linked list problems test your understanding of pointers and edge cases. In real systems, they're common in kernel code, memory allocators, and anywhere you need dynamic, efficient insertion and deletion.

The two-pointer techniques we've covered are fundamental. Master them, and you'll find yourself reaching for them instinctively when you encounter list-based problems.