Fast slow pointer

Find Middle of Linked List

syntax

Slow pointer moves 1 step, fast moves 2 steps.
When fast reaches end, slow is at the middle.

example

// JavaScript
function findMiddle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

# Python
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

output

1→2→3→4→5 → middle is 3
1→2→3→4 → middle is 3 (second of two middles)

Note Time O(n), Space O(1). For even-length lists, this returns the second middle node. To get the first middle, use: while fast.next and fast.next.next. This technique is a building block for merge sort on linked lists and palindrome checking.

Pattern: Fast & Slow Pointer

DSA · Common Patterns Summary

syntax

When to use:
- Cycle detection (linked list, array)
- Finding middle of linked list
- Finding the start of a cycle
- Happy number problem

Slow moves 1 step, fast moves 2 steps.

example

// JavaScript — Happy number (sum of squared digits eventually reaches 1)
function isHappy(n) {
  function digitSquareSum(num) {
    let sum = 0;
    while (num > 0) {
      const digit = num % 10;
      sum += digit * digit;
      num = Math.floor(num / 10);
    }
    return sum;
  }
  let slow = n, fast = n;
  do {
    slow = digitSquareSum(slow);
    fast = digitSquareSum(digitSquareSum(fast));
  } while (slow !== fast);
  return slow === 1;
}

# Python
def is_happy(n):
    def digit_square_sum(num):
        total = 0
        while num > 0:
            digit = num % 10
            total += digit * digit
            num //= 10
        return total
    slow = fast = n
    while True:
        slow = digit_square_sum(slow)
        fast = digit_square_sum(digit_square_sum(fast))
        if slow == fast:
            break
    return slow == 1

output

is_happy(19) → True (19→82→68→100→1)
is_happy(2) → False (enters cycle)

Note The fast/slow pointer pattern detects cycles in any sequence where each value maps to the next. It uses O(1) space compared to a hash set. For linked lists, this is Floyd's algorithm. For number sequences (like happy number), the function that generates the next value plays the role of 'next pointer'.

DSAInterview Prep