Find middle element of a linked list: slow/fast pointer

• Slow pointer moves one node forward each iteration: slow = slow.next.
• Fast pointer moves two nodes forward each iteration: fast = fast.next.next.
• When fast == null or fast.next == null, slow is at the middle of the list.
• O(n) time, O(1) space: single pass, no extra data structures, no need to know the list length.
• For even-length lists, slow lands on the second of the two middle nodes.
• This is the tortoise-and-hare algorithm, also used for cycle detection (Floyd's algorithm).

What is the slow/fast pointer technique?

The slow/fast pointer (tortoise and hare) technique finds the middle of a singly linked list in one pass without knowing the list length. The key invariant: when fast has moved 2k steps, slow has moved k steps, so slow is always at half the distance fast has traveled.

How do you implement it?

package com.bank.util;

public class LinkedListMiddleDemo {
    static class Node {
        int value;
        Node next;

        Node(int value) { this.value = value; }
        Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    public static Node findMiddle(Node head) {
        if (head == null) return null;

        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;  // middle node
    }

    public static void main(String[] args) {
        // Linked list: 100 -> 200 -> 300 -> 400 -> 500
        Node head = new Node(100,
            new Node(200,
                new Node(300,
                    new Node(400,
                        new Node(500)))));

        Node middle = findMiddle(head);
        System.out.println("Middle: " + middle.value);
    }
}

Middle: 300

What happens with even-length lists?

// Even-length: 100 -> 200 -> 300 -> 400
// Step 0: slow=100, fast=100
// Step 1: slow=200, fast=300
// Step 2: slow=300, fast=null (fast.next.next past end)
// Middle: 300 (second of the two middle nodes 200, 300)

The convention fast != null && fast.next != null lands slow on the second middle node. To land on the first middle node, use fast.next != null && fast.next.next != null.

How does this relate to cycle detection?

The same technique powers Floyd's cycle detection: if the list has a cycle, the fast pointer eventually catches the slow pointer from behind. If there is no cycle, fast reaches the end.

Why are streams not suitable here?

Streams require a source that produces elements sequentially. A singly linked list does not implement Iterable or Spliterator by default. More importantly, finding the middle requires two moving pointers with mutable state, which does not fit the stateless-function model of streams.

What are edge cases?

// Single node: middle is itself
Node single = new Node(42);
findMiddle(single);  // 42

// Two nodes: 10 -> 20
// slow=10, fast=10
// Step 1: slow=20, fast=null
// Middle: 20 (second node)

// Null head: returns null
findMiddle(null);  // null

What should a senior engineer know?

• The slow/fast technique also finds the kth node from the end: start fast k steps ahead, then move both one step at a time. When fast reaches the end, slow is at the kth-from-end node.
• For java.util.LinkedList, you can use list.get(list.size() / 2), but that is O(n/2) random access on a linked list, which is O(n) anyway. The slow/fast approach is O(n) on a raw linked list without random access.
• In banking, a transaction history as a linked list can find the median-position entry for an auditor in a single traversal without buffering the whole list.