Lesson 8.4 · Linked Lists

Fast and Slow Pointers

One pointer moves one step, the other two. They reveal the middle of a list and detect cycles in O(1) space (Floyd's algorithm).

14 min

Think of it like this

Two runners on a track. On a straight road, the fast one reaches the end while the slow one is halfway: that's the middle. On a circular track, the fast one eventually laps the slow one: that's a cycle.

1.Finding the middle

Move slow one step and fast two steps while fast and fast.next exist. When fast reaches the end, slow is at the middle (the second middle for even lengths).

▶ Dry run: Middle of five nodeshead = 1 → 2 → 3 → 4 → 5

↑slow↑fast

null

Step 1/3Both start at the head.

2.Detecting a cycle (Floyd)

If the list has a cycle, both pointers eventually enter it, and the fast one gains one step per move on the slow one, so they must meet. If there's no cycle, the fast pointer reaches null. O(n) time, O(1) space, versus O(n) space for a HashSet of visited nodes.

To find where the cycle starts: after they meet, move one pointer back to the head and advance both one step at a time; they meet at the cycle's start. (If the tail before the cycle has length a and they met b steps into the cycle of length c, then a ≡ c − b (mod c).)

Main.java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Main {
    static boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
    public static void main(String[] args) {
        ListNode a = new ListNode(3), b = new ListNode(2), c = new ListNode(0), d = new ListNode(-4);
        a.next = b; b.next = c; c.next = d;
        System.out.println(hasCycle(a));
        d.next = b;                       // tail points back to node 2: a cycle
        System.out.println(hasCycle(a));
    }
}

Output

false
true

Remember

slow +1, fast +2; loop while fast != null && fast.next != null.
Fast hits null → no cycle; they meet → cycle.
Reset one to head and step both by 1 to find the cycle start.

Common mistakes

Checking only fast.next != null (NullPointerException when fast itself is null).
Comparing values instead of node references to detect a meeting.

Command Palette

Fast and Slow Pointers

1.Finding the middle

2.Detecting a cycle (Floyd)