Find the Middle Element of a Linked List: Slow/Fast Pointer

• Fast-slow pointer – a technique where two pointers traverse at different speeds to find positional information.
• Slow pointer – advances one node per iteration.
• Fast pointer – advances two nodes per iteration.
• Termination – when fast reaches the end, slow is at the middle.
• Complexity – O(n) time, O(1) space, single pass without counting length.

What is the problem?

Given the head of a singly linked list, return the middle node. If there are two middle nodes (even length), return the second one.

At the National Bank of India, the audit tool needs the middle transaction from a chain for a quick sampling check, without scanning the chain twice.

How does the fast-slow pointer technique work?

Start both pointers at the head. Advance slow by one and fast by two each iteration. When fast reaches the end, slow is at the middle.

package com.bank.service;

public class MiddleOfLinkedList {
    public static ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        // Build: 100 -> 200 -> 300 -> 400 -> 500
        ListNode head = new ListNode(100,
            new ListNode(200, new ListNode(300,
                new ListNode(400, new ListNode(500)))));
        System.out.println("Middle: " + findMiddle(head).val);
    }
}

Middle: 300

Why does this work?

When the fast pointer moves two steps for every one step of the slow pointer, by the time fast has traversed the full list, slow has traversed exactly half. This is a simple mathematical relationship: if fast travels distance d, slow travels d/2.

What about odd vs even length?

For odd length [1, 2, 3, 4, 5]: slow lands on 3 (the single middle).
For even length [1, 2, 3, 4]: slow lands on 3 (the second of the two middles).

// Odd: 1 -> 2 -> 3 -> 4 -> 5
// Iteration 1: slow=2, fast=3
// Iteration 2: slow=3, fast=5
// fast.next is null -> stop. slow = 3 (middle)

// Even: 1 -> 2 -> 3 -> 4
// Iteration 1: slow=2, fast=3
// Iteration 2: slow=3, fast=null
// fast is null -> stop. slow = 3 (second middle)

How to find the first middle for even lists?

Start fast at head.next instead of head, or change the loop condition to fast.next != null && fast.next.next != null.

// Second middle (standard)
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) { ... }
// For [1,2,3,4]: returns 3

// First middle (variant)
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) { ... }
// For [1,2,3,4]: returns 2

Why does the guard order matter?

The condition fast != null && fast.next != null must check fast != null first. If fast is null, accessing fast.next would throw a NullPointerException. Java's short-circuit evaluation ensures the second check is skipped when the first fails.

// Wrong: crashes on even-length lists
while (fast.next != null && fast != null) { ... }
// fast could be null before we check fast.next

// Correct: check fast first
while (fast != null && fast.next != null) { ... }

What is the time and space complexity?

| Approach | Time | Space | Passes |
|---|---|---|---|
| Fast-slow pointer | O(n) | O(1) | 1 |
| Count length then walk half | O(n) | O(1) | 2 |

Both are O(n), but the fast-slow approach does it in a single pass.

What are common mistakes?

Reversing the guard order, which causes a NullPointerException on even-length lists.

Another mistake is forgetting that this formulation returns the second middle on even lists, when the problem asks for the first.

What are the edge cases?

• Empty list (null head): return null.
• Single node: return that node.
• Two nodes: return the second node (with standard formulation).

What should a senior engineer know?

The fast-slow skeleton is a building block. Recognizing it connects multiple problems:

• Cycle detection: if fast catches slow, there is a cycle.
• Cycle start: reset one pointer to head after detection and advance both at speed one.
• Palindrome check: find middle, reverse second half, compare.
• List splitting: use the middle to split the list into two halves for merge sort.

What are common interview follow-up questions?

• What if you need the first middle on even lists? (Start fast at head.next.)
• How does this help with merge sort on linked lists? (Split at the middle, sort both halves, merge.)
• Can you detect a cycle with this technique? (Yes, if slow and fast meet, there is a cycle.)