Fast and Slow Pointers: Cycle Detection and Middle Node

The fast and slow pointers technique (also called Floyd’s tortoise and hare) runs two pointers through a linked list at different speeds — one moving one step at a time, the other two steps. Their relative motion reveals structure you otherwise couldn’t see in a single forward pass: whether the list has a cycle, and where its middle is — all in O(n) time and O(1) space. It is one of the most reused patterns in DSA.

Finding the middle node

Move slow by one and fast by two. When fast reaches the end, slow has covered exactly half the distance, so it sits on the middle. For an even-length list this lands on the second of the two middle nodes.

Node* middle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;        // 1 step
        fast = fast->next->next;  // 2 steps
    }
    return slow;
}

Node middle(Node head) {
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;         // 1 step
        fast = fast.next.next;    // 2 steps
    }
    return slow;
}

function middle(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;        // 1 step
    fast = fast.next.next;   // 2 steps
  }
  return slow;
}

def middle(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next        # 1 step
        fast = fast.next.next   # 2 steps
    return slow

For beginners: Why does this work? In the time it takes fast to walk the whole list, slow walks half of it. Speed two versus speed one means slow ends at the halfway mark — no length counting required.

Detecting a cycle

If the list loops back on itself, the fast pointer eventually laps the slow pointer and they collide. If there is no cycle, fast simply runs off the end. This is Floyd’s cycle detection.

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;  // same node => cycle
    }
    return false;
}

boolean hasCycle(Node head) {
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;  // same node => cycle
    }
    return false;
}

function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;  // same node => cycle
  }
  return false;
}

def has_cycle(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:        # same node => cycle
            return True
    return False

Why a cycle guarantees a collision

Once both pointers are inside the loop, each step closes the gap between them by exactly one node (fast gains one per step). A gap that shrinks by one every step must hit zero — they cannot jump past each other — so a meeting is inevitable. Without a cycle, fast hits null and the loop ends.

Finding where the cycle begins

After a collision, reset one pointer to the head and advance both by one step. They meet again exactly at the cycle’s entry node — a clean consequence of the distances involved.

Node* cycleStart(Node* head) {
    Node* slow = head; Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) {                 // collision
            Node* p = head;
            while (p != slow) { p = p->next; slow = slow->next; }
            return p;                       // entry node
        }
    }
    return nullptr;                         // no cycle
}

Node cycleStart(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
        if (slow == fast) {                 // collision
            Node p = head;
            while (p != slow) { p = p.next; slow = slow.next; }
            return p;                       // entry node
        }
    }
    return null;                            // no cycle
}

function cycleStart(head) {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next; fast = fast.next.next;
    if (slow === fast) {                    // collision
      let p = head;
      while (p !== slow) { p = p.next; slow = slow.next; }
      return p;                             // entry node
    }
  }
  return null;                              // no cycle
}

def cycle_start(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:                    # collision
            p = head
            while p is not slow:
                p = p.next
                slow = slow.next
            return p                        # entry node
    return None                             # no cycle

Complexity

Task	Time	Space
Find middle	O(n)	O(1)
Detect cycle	O(n)	O(1)
Find cycle start	O(n)	O(1)

The O(1) space is the whole point. You could detect a cycle by storing every visited node in a hash set — also O(n) time — but that costs O(n) memory. Two pointers do it with none.

Pitfall: The loop guard must be fast != null && fast.next != null, in that order. Checking fast.next first can dereference null on an even-length list and crash. Short-circuit evaluation saves you only if fast != null is tested first.

Where the pattern reappears

Fast/slow pointers power palindrome checks (find the middle, reverse the back half, compare), removing the Nth node from the end (gap of N between the pointers), and many array problems too — see the fast & slow pointers pattern. Practice it now in the linked list exercises.