Middle of the LinkedList (Fast and Slow Pointers)

• Fast-slow pointers use two pointers that start at the head and advance at different speeds.
• Speed ratio of 2:1 means when the fast pointer reaches the end, the slow pointer has covered exactly half the distance.
• Even-length lists have two middle candidates; the standard loop condition returns the second middle node.
• Single pass means you never need to count the total nodes first, unlike the two-pass approach.
• Constant space uses only two pointer variables regardless of list length.

What is the Middle of the LinkedList problem?

Given the head of a singly linked list, return the middle node. If the list has an even number of nodes, return the second of the two middle nodes. Solve it in a single pass without knowing the length in advance.

For example, given 1 -> 2 -> 3 -> 4 -> 5, the middle is node 3. For 1 -> 2 -> 3 -> 4, the two middles are nodes 2 and 3, and we return node 3 (the second middle).

package com.bank.service;

/**
 * Linked list node representing a statement page.
 */
public class StatementPage {
    int pageNumber;
    StatementPage next;

    public StatementPage(int pageNumber) {
        this.pageNumber = pageNumber;
    }
}

package com.bank.service;

/**
 * Finds the middle node of a singly linked list
 * using the fast-slow pointer technique.
 */
public class MiddlePageFinder {

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

        StatementPage slow = head;
        StatementPage fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        // Build: P1 -> P2 -> P3 -> P4 -> P5
        StatementPage p1 = new StatementPage(1);
        StatementPage p2 = new StatementPage(2);
        StatementPage p3 = new StatementPage(3);
        StatementPage p4 = new StatementPage(4);
        StatementPage p5 = new StatementPage(5);
        p1.next = p2; p2.next = p3; p3.next = p4; p4.next = p5;

        StatementPage middle = findMiddle(p1);
        System.out.println("Middle page: " + middle.pageNumber);
    }
}

Middle page: 3

Why does the fast-slow technique work?

The fast pointer moves at twice the speed of the slow pointer. After k iterations, slow has moved k nodes forward and fast has moved 2k nodes forward. When fast reaches the end of the list (after n/2 iterations), slow has moved n/2 nodes, placing it at the middle.

This works because of a simple mathematical relationship: if the fast pointer covers the entire list in t steps, the slow pointer covers exactly half the list in the same t steps.

// Mathematical reasoning:
// List length = n
// After t iterations: slow at position t, fast at position 2t
// Fast reaches end when 2t >= n, so t = n/2
// At that point, slow is at position n/2, the middle

How is this different from the two-pass approach?

The two-pass approach first counts all nodes, then walks to position count / 2. It is correct but requires two full traversals. The fast-slow approach does it in a single pass.

| Aspect | Two-pass approach | Fast-slow approach |
|---|---|---|
| Passes | Two (count + walk) | One |
| Time | O(n) | O(n) |
| Space | O(1) | O(1) |
| When list is a stream | Cannot rewind | Works in one pass |
| Code complexity | Simple but longer | Compact |

// Two-pass approach
public static StatementPage findMiddleTwoPass(StatementPage head) {
    // Pass 1: count nodes
    int count = 0;
    StatementPage current = head;
    while (current != null) {
        count++;
        current = current.next;
    }

    // Pass 2: walk to middle
    current = head;
    for (int i = 0; i < count / 2; i++) {
        current = current.next;
    }
    return current;
}

// Fast-slow approach (single pass)
public static StatementPage findMiddleSinglePass(StatementPage head) {
    StatementPage slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

What happens with even-length lists?

For even-length lists, there are two middle candidates. The standard loop condition while (fast != null && fast.next != null) returns the second middle.

For the list P1 -> P2 -> P3 -> P4, the two middles are P2 and P3. With the standard condition, fast starts at P1, moves to P3 on the first iteration, then to null (past P4) on the second attempt, but fast.next is null so the loop stops. At that point slow is at P3, the second middle.

To get the first middle instead, change the loop condition to while (fast.next != null && fast.next.next != null). This stops one step earlier.

// Second middle (standard)
public static StatementPage findSecondMiddle(StatementPage head) {
    StatementPage slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow; // P3 for [P1, P2, P3, P4]
}

// First middle (tighter loop)
public static StatementPage findFirstMiddle(StatementPage head) {
    StatementPage slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow; // P2 for [P1, P2, P3, P4]
}

List: P1 -> P2 -> P3 -> P4
Second middle: P3
First middle: P2

What are the edge cases?

The edge cases to handle are:

• Null head: return null. The list is empty.
• Single node: slow and fast both stay at the head. The middle of a one-node list is that node.
• Two nodes: fast moves to the second node, fast.next is null, loop stops. Slow is at the second node, which is the second middle.

package com.bank.service;

public class MiddleEdgeCases {
    public static void main(String[] args) {
        // Null head
        System.out.println("Null: " + MiddlePageFinder.findMiddle(null));

        // Single node
        StatementPage single = new StatementPage(1);
        System.out.println("Single: " + MiddlePageFinder.findMiddle(single).pageNumber);

        // Two nodes
        StatementPage a = new StatementPage(1);
        StatementPage b = new StatementPage(2);
        a.next = b;
        System.out.println("Two nodes: " + MiddlePageFinder.findMiddle(a).pageNumber);
    }
}

Null: null
Single: 1
Two nodes: 2

What are common mistakes?

The most common mistake is getting the loop condition wrong, which causes a NullPointerException when fast or fast.next is null.

// WRONG: checking only fast.next, not fast itself
while (fast.next != null) { // BUG: crashes if fast is null
    slow = slow.next;
    fast = fast.next.next;
}
// For an even-length list, fast becomes null after the last step,
// and the next iteration tries fast.next on a null reference.

// CORRECT: check both fast and fast.next
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// The short-circuit && ensures fast is checked for null first

Another mistake is moving fast before slow, which does not change the result but makes the code harder to reason about. Always move them in the natural order: slow first, then fast.

How is this used as a building block?

Finding the middle is the first step in several important linked list algorithms:

• Palindrome check: find the middle, reverse the second half, compare both halves.
• List reordering: find the middle, reverse the second half, zip the two halves together.
• Merge sort on linked lists: find the middle, split the list into two halves, recursively sort each half, merge.

// Palindrome check using middle finder
public static boolean isPalindrome(StatementPage head) {
    StatementPage middle = findMiddle(head);
    StatementPage reversedSecondHalf = reverse(middle);

    StatementPage p1 = head;
    StatementPage p2 = reversedSecondHalf;
    while (p2 != null) {
        if (p1.pageNumber != p2.pageNumber) return false;
        p1 = p1.next;
        p2 = p2.next;
    }
    return true;
}

private static StatementPage reverse(StatementPage head) {
    StatementPage prev = null, curr = head;
    while (curr != null) {
        StatementPage next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

What should a senior engineer know?

A senior engineer should know that the exact loop condition determines which middle node is returned for even-length lists, and interviewers often probe this specific detail. Stating the convention explicitly rather than leaving it implicit shows precision.

The fast-slow pattern also extends beyond finding the middle:

• Cycle detection: Floyd's algorithm uses fast and slow pointers to detect cycles in a linked list.
• Finding the cycle start: after detecting a cycle, reset one pointer to the head and advance both one step at a time until they meet at the cycle start.
• Finding the kth node from the end: use two pointers separated by k nodes.

In banking systems, linked lists appear in transaction chains, statement page sequences, and audit trails where the data structure must support efficient traversal without random access.

What are common interview follow-up questions?

Interviewers often ask:

• How would you return the first middle instead of the second? Change the loop condition.
• Can you find the middle of a circular linked list? Yes, but you need to detect the cycle first and count the cycle length.
• What if the list is doubly linked? You can use two pointers from both ends moving inward, but the fast-slow technique still works and uses less information.
• How does this relate to the tortoise and hare algorithm? They are the same technique. The tortoise is the slow pointer and the hare is the fast pointer.