Find Middle of Linked List — Concurrent Mutation Bug

Finding the middle of a linked list is one of those problems that looks trivial until you actually sit down to solve it. You can't just do list[length/2] like you would with an array — linked lists don't give you random access. Every node only knows about the next node, so you have to walk the chain step by step. This constraint shows up constantly in real software: playlist management, undo history stacks, browser cache chains, and operating system task queues all use linked structures where random access is expensive or impossible.

The naive solution — count all nodes, then walk to the middle — works, but it requires two full passes over the list. In performance-critical code, two passes when one will do is a red flag. The elegant solution uses two pointers moving at different speeds, finding the middle in a single pass. This 'fast and slow pointer' pattern doesn't just solve this one problem either — it's the foundation for detecting cycles in linked lists, finding the nth node from the end, and several other classic problems you'll see in interviews.

By the end of this article, you'll be able to write a clean, single-pass solution to find the middle of any linked list from memory. You'll understand exactly why it works (not just that it works), spot the two most common mistakes beginners make, and confidently answer interview questions on this topic. Let's build it from the ground up.

Why Finding the Middle of a Linked List Is a Concurrency Trap

Finding the middle node of a singly linked list is a classic two-pointer problem: move a slow pointer one step and a fast pointer two steps per iteration. When the fast pointer reaches the end, the slow pointer lands at the middle. This runs in O(n) time with O(1) extra space — optimal for a single-threaded traversal.

In practice, the algorithm assumes the list structure is immutable during traversal. If another thread concurrently mutates the list — inserting, deleting, or rearranging nodes — the fast pointer can skip over or land on a node that no longer exists, causing a NullPointerException or an infinite loop. The two-pointer technique is not atomic; between the slow and fast moves, the list can change.

Use this algorithm only when you control the list’s lifecycle — e.g., during initialization, in a single-threaded context, or under a read lock. In concurrent systems, prefer a snapshot or a synchronized traversal. Many teams discover this the hard way when a seemingly simple utility crashes under load.

How to Find the Middle of a Linked List — Algorithm

Use the fast/slow pointer (tortoise and hare) technique to find the middle in O(n) time with O(1) space — no need to count length first.

Algorithm: 1. Initialize slow = head, fast = head. 2. While fast is not null and fast.next is not null: a. slow = slow.next. b. fast = fast.next.next. 3. When the loop ends, slow is at the middle.

Worked example — list: 1->2->3->4->5: Step 1: slow=1, fast=1. Step 2: slow=2, fast=3. Step 3: slow=3, fast=5. fast.next = null. Loop ends. Middle = slow = node 3.

For even length (1->2->3->4): Step 1: slow=1, fast=1. Step 2: slow=2, fast=3. fast.next.next = null. Loop ends. Middle = node 2 (first of two centers). To get the second center, change condition to while fast.next is not null.

This technique is used in merge sort on linked lists and palindrome checking on linked lists.

What Is a Linked List — A Quick Ground-Up Recap

Before we find the middle of something, we need to be crystal clear on what that something actually is.

An array stores elements in one contiguous block of memory — like numbered seats in a cinema row. A linked list is different. Each element lives in its own separate box called a node, and each node holds two things: the actual data (say, a number or a name), and a pointer — basically an arrow — that points to the next node in the chain. The last node's arrow points to null, meaning 'the chain ends here'.

Think of it like a treasure hunt. Each clue (node) tells you the answer AND gives you directions to the next clue. You can't skip to clue 7 without following clues 1 through 6 first. That's the key constraint.

In Java, a single node looks like this: a class with an integer value field and a next field that points to another node. The entire list is represented by just one thing — a reference to the very first node, called the head. If you lose the head reference, you lose the whole list.

package io.thecodeforge.linkedlist;

// A single node in a linked list.
// Each node holds a piece of data AND a reference to the next node.
public class LinkedListNode {

    int data;               // The actual value stored in this node
    LinkedListNode next;    // Arrow pointing to the next node (null if this is the last node)

    // Constructor: creates a new node with the given value.
    // When first created, next is automatically null — it points nowhere yet.
    public LinkedListNode(int data) {
        this.data = data;
        this.next = null;
    }

    // --- Quick demo to visualise a simple linked list ---
    public static void main(String[] args) {

        // Build the list: 10 -> 20 -> 30 -> 40 -> 50 -> null
        LinkedListNode head = new LinkedListNode(10); // head always points to the first node
        head.next = new LinkedListNode(20);
        head.next.next = new LinkedListNode(30);
        head.next.next.next = new LinkedListNode(40);
        head.next.next.next.next = new LinkedListNode(50);

        // Walk the list from head to tail and print each value
        LinkedListNode current = head; // start at the beginning
        System.out.print("List: ");
        while (current != null) {      // keep going until we fall off the end
            System.out.print(current.data + " -> ");
            current = current.next;    // move to the next node
        }
        System.out.println("null");
    }
}

The Naive Approach — Count First, Then Walk (Two Passes)

The first solution most beginners reach for is completely logical: count all the nodes to get the total length, divide by two to get the middle index, then walk to that index. Nothing wrong with that thinking — it works correctly every time.

Here's how it plays out: if the list has 5 nodes, middle index = 5/2 = 2 (zero-based), so the third node is the middle. If the list has 6 nodes, there are technically two middle nodes — convention in most interviews and problems is to return the second middle (index 3), but confirm this with your interviewer.

The downside is that this makes two full passes over the list. For a list with a million nodes, that's two million pointer hops. In a performance-sensitive environment — a real-time system, or a function called thousands of times per second — that cost adds up. More importantly, in an interview, proposing a two-pass solution before a one-pass solution signals that you haven't pushed your thinking far enough.

Still, write the naive solution first. It shows you understand the problem, and it gives you a correctness baseline to test against your optimised version.

package io.thecodeforge.linkedlist;

public class FindMiddleNaive {

    // --- Node definition (self-contained for easy copy-paste) ---
    static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
        }
    }

    // Finds the middle node using two passes.
    // Pass 1: count how many nodes exist.
    // Pass 2: walk to the middle index.
    static Node findMiddleTwoPass(Node head) {
        if (head == null) {
            return null; // empty list — nothing to find
        }

        // --- Pass 1: Count all nodes ---
        int totalNodes = 0;
        Node counter = head;         // use a separate pointer so we preserve head
        while (counter != null) {
            totalNodes++;            // count this node
            counter = counter.next;  // move to the next node
        }

        // Calculate the middle index.
        // For even-length lists (e.g., 6 nodes), 6/2 = 3, which gives the SECOND middle.
        // Integer division in Java truncates, so 5/2 = 2 (third node, zero-based) — correct.
        int middleIndex = totalNodes / 2;

        // --- Pass 2: Walk to the middle index ---
        Node current = head;
        for (int step = 0; step < middleIndex; step++) {
            current = current.next;  // take one step forward
        }

        return current; // this node is the middle
    }

    // --- Helper: build a linked list from an array of values ---
    static Node buildList(int[] values) {
        Node dummyHead = new Node(0); // placeholder to simplify building
        Node tail = dummyHead;
        for (int value : values) {
            tail.next = new Node(value);
            tail = tail.next;
        }
        return dummyHead.next; // return actual first node, not the dummy
    }

    public static void main(String[] args) {

        // Test 1: Odd number of nodes (clear single middle)
        Node oddList = buildList(new int[]{10, 20, 30, 40, 50});
        Node middleOdd = findMiddleTwoPass(oddList);
        System.out.println("Odd list  (10->20->30->40->50): Middle = " + middleOdd.data);

        // Test 2: Even number of nodes (two possible middles — we return the second)
        Node evenList = buildList(new int[]{10, 20, 30, 40, 50, 60});
        Node middleEven = findMiddleTwoPass(evenList);
        System.out.println("Even list (10->20->30->40->50->60): Middle = " + middleEven.data);

        // Test 3: Single node — should return that node itself
        Node singleNode = buildList(new int[]{42});
        Node middleSingle = findMiddleTwoPass(singleNode);
        System.out.println("Single node list (42): Middle = " + middleSingle.data);
    }
}

The Elegant Solution — Fast and Slow Pointers (One Pass)

Here's where it gets beautiful. Remember the two-walkers analogy? One walker moves one step at a time — that's the slow pointer. The other moves two steps at a time — that's the fast pointer. Both start at the head. You keep moving them until the fast pointer reaches the end of the list. At that exact moment, the slow pointer is sitting right in the middle.

Why does this work mathematically? When fast has travelled N steps, slow has travelled N/2 steps. If fast reaches the end (N = total length), slow is at position N/2 — the middle. It's essentially doing the division for you, in real-time, without ever counting the length.

The one subtle detail is the stopping condition. You stop when fast reaches null (the end) OR when fast.next is null (fast is on the last node). If you only check fast != null, you risk fast jumping to null and then trying to access fast.next on the next iteration — which throws a NullPointerException. This is the most common mistake beginners make with this algorithm, so pay close attention to the stopping condition in the code below.

This pattern — the fast/slow pointer — is one of the most versatile tools in DSA. Once you internalize it here, you'll recognize it in cycle detection, palindrome checking, and reordering problems.

package io.thecodeforge.linkedlist;

public class FindMiddleFastSlow {

    // --- Node definition ---
    static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
        }
    }

    // Finds the middle node in ONE pass using the fast/slow pointer technique.
    //
    // VISUAL for list 10->20->30->40->50:
    //
    // Start:   slow=10,  fast=10
    // Step 1:  slow=20,  fast=30   (slow moves +1, fast moves +2)
    // Step 2:  slow=30,  fast=50   (slow moves +1, fast moves +2)
    // fast.next is null, so we STOP. slow=30 is the middle. ✓
    //
    static Node findMiddleFastSlow(Node head) {
        if (head == null) {
            return null; // empty list guard
        }

        Node slowPointer = head; // moves 1 step at a time
        Node fastPointer = head; // moves 2 steps at a time

        // Keep moving until fast pointer reaches the end.
        // We check BOTH conditions to avoid NullPointerException:
        //   - fastPointer != null       -> fast hasn't fallen off the end
        //   - fastPointer.next != null  -> fast can safely take TWO steps
        while (fastPointer != null && fastPointer.next != null) {
            slowPointer = slowPointer.next;       // slow takes 1 step
            fastPointer = fastPointer.next.next;  // fast takes 2 steps
        }

        // When the loop ends, slowPointer is exactly at the middle.
        return slowPointer;
    }

    // --- Helper: print list values for easy visualisation ---
    static void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.data);
            if (current.next != null) System.out.print(" -> ");
            current = current.next;
        }
        System.out.println();
    }

    // --- Helper: build list from int array ---
    static Node buildList(int[] values) {
        Node dummy = new Node(0);
        Node tail = dummy;
        for (int val : values) {
            tail.next = new Node(val);
            tail = tail.next;
        }
        return dummy.next;
    }

    public static void main(String[] args) {

        // Test 1: 5 nodes — middle is the 3rd node (30)
        Node list1 = buildList(new int[]{10, 20, 30, 40, 50});
        System.out.print("List 1: "); printList(list1);
        System.out.println("Middle: " + findMiddleFastSlow(list1).data);
        System.out.println();

        // Test 2: 6 nodes — two middles, we return the SECOND (40)
        Node list2 = buildList(new int[]{10, 20, 30, 40, 50, 60});
        System.out.print("List 2: "); printList(list2);
        System.out.println("Middle: " + findMiddleFastSlow(list2).data);
        System.out.println();

        // Test 3: 1 node — the only node is the middle
        Node list3 = buildList(new int[]{99});
        System.out.print("List 3: "); printList(list3);
        System.out.println("Middle: " + findMiddleFastSlow(list3).data);
        System.out.println();

        // Test 4: 2 nodes — second node is the middle (even list convention)
        Node list4 = buildList(new int[]{5, 15});
        System.out.print("List 4: "); printList(list4);
        System.out.println("Middle: " + findMiddleFastSlow(list4).data);
    }
}

Stepping Through the Algorithm — Visual Dry Run

Reading code is one thing; watching it execute step by step is how it actually sticks. Let's dry-run the fast/slow pointer algorithm on a 5-node list so there's zero ambiguity about what's happening at each moment.

Our list: 10 → 20 → 30 → 40 → 50 → null

Before the loop starts, both slow and fast are pointing at node 10 (the head). Now the loop checks: fast (10) is not null, and fast.next (20) is not null — condition passes, we enter the loop.

Iteration 1: slow moves to 20, fast jumps to 30. Check: fast (30) is not null, fast.next (40) is not null — condition passes.

Iteration 2: slow moves to 30, fast jumps to 50. Check: fast (50) is not null, but fast.next is null — condition FAILS. Loop exits.

Slow is at 30 — the middle node. Done.

Now let's check the even-length case: 10 → 20 → 30 → 40 → null (4 nodes). Start: slow=10, fast=10. Iter 1: slow=20, fast=30. Iter 2: slow=30, fast=null. fast is null — loop exits. Slow is at 30, which is the second of the two middle nodes (30 and 20). This matches the expected convention perfectly.

package io.thecodeforge.linkedlist;

public class DryRunVisualised {

    static class Node {
        int data;
        Node next;
        Node(int data) { this.data = data; }
    }

    // Same algorithm as before, with step-by-step print statements
    // so you can watch EXACTLY what happens on each iteration.
    static Node findMiddleWithTrace(Node head) {
        if (head == null) return null;

        Node slowPointer = head;
        Node fastPointer = head;

        int step = 0;
        System.out.printf("%-8s %-12s %-12s%n", "Step", "Slow", "Fast");
        System.out.printf("%-8s %-12s %-12s%n", "------", "----------", "----------");
        System.out.printf("%-8s %-12s %-12s%n", "Start",
            slowPointer.data,
            fastPointer.data);

        while (fastPointer != null && fastPointer.next != null) {
            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next.next;
            step++;

            // Print current state after each move
            System.out.printf("%-8s %-12s %-12s%n",
                "Step " + step,
                slowPointer.data,
                (fastPointer != null ? fastPointer.data : "null"));
        }

        System.out.println();
        return slowPointer;
    }

    static Node buildList(int[] values) {
        Node dummy = new Node(0);
        Node tail = dummy;
        for (int val : values) {
            tail.next = new Node(val);
            tail = tail.next;
        }
        return dummy.next;
    }

    public static void main(String[] args) {

        System.out.println("=== ODD LIST: 10 -> 20 -> 30 -> 40 -> 50 ===");
        Node oddList = buildList(new int[]{10, 20, 30, 40, 50});
        Node result1 = findMiddleWithTrace(oddList);
        System.out.println("Middle node value: " + result1.data);

        System.out.println();

        System.out.println("=== EVEN LIST: 10 -> 20 -> 30 -> 40 ===");
        Node evenList = buildList(new int[]{10, 20, 30, 40});
        Node result2 = findMiddleWithTrace(evenList);
        System.out.println("Middle node value: " + result2.data);
    }
}

When to Use Fast/Slow Pointer in Production

The fast/slow pointer technique isn't just for coding interviews. It shows up in real systems wherever you need to find a midpoint without knowing the total size in advance.

Playlist shuffle. Streaming audio or video services often use linked lists for queues. When the user hits shuffle, the algorithm needs to split the list at its midpoint to interleave halves. Using two passes would introduce perceptible lag for playlists with thousands of tracks.

Memory defragmentation. Some custom allocators manage free space as a linked list. Finding the middle to balance fragmentation requires a single-pass midpoint search — the fast/slow pointer is a natural fit.

Database query result pagination. When a query returns a cursor-based linked set of rows, the middle page can be found efficiently without counting the total result count (which may be expensive).

The key constraint in all these cases: you don't know the total size beforehand, and you cannot afford two traversals. The fast/slow pointer delivers the middle in a single pass with zero extra memory.

Two Passes? Fine for Homework, Not for Production

The naive approach is exactly what it sounds like: count every node in a first pass, then walk to the halfway point in a second pass. It works. It passes LeetCode. But it's also a clear signal you haven't thought about the problem deeply.

Here's why it stinks: you're touching every node twice. In a production system serving thousands of requests per second, that doubles your cache misses, doubles your pointer chasing, and doubles the time your thread spends fighting for memory bandwidth. When the list lives across scattered heap locations (which it always does in real workloads), the second pass is a full cache reload.

Time complexity is O(n) — same as the fast/slow pointer — but the constant factor is 2x. Space is O(1). That's the only good thing you can say about it. If you're writing a one-off script to inspect a debug payload, fine. If you're shipping this in a latency-sensitive path, your on-call rotation will hate you.

// io.thecodeforge — dsa tutorial

public class TwoPassMiddle {
    static class Node {
        int data;
        Node next;
        Node(int data) { this.data = data; }
    }

    public static Node findMiddle(Node head) {
        if (head == null) return null;
        int count = 0;
        Node current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        int mid = count / 2;
        current = head;
        for (int i = 0; i < mid; i++) {
            current = current.next;
        }
        return current;
    }

    public static void main(String[] args) {
        Node head = new Node(10);
        head.next = new Node(20);
        head.next.next = new Node(30);
        head.next.next.next = new Node(40);
        head.next.next.next.next = new Node(50);
        System.out.println("Middle: " + findMiddle(head).data);
    }
}

Fast and Slow Pointer: The One-Pass Hack That Actually Works

This is the hare and tortoise algorithm, and it's one of those rare patterns that's both elegant and brutally practical. Two pointers. One moves one step per iteration, the other moves two. When the fast pointer hits the end, the slow pointer is dead center. That's it.

Why does this work? Because the fast pointer covers distance at double the rate. When it's traversed the whole list (length L), the slow pointer has covered L/2 — exactly the middle. For even-length lists, this lands on the second middle node because the fast pointer needs exactly L/2 steps to reach null, and slow moves L/2 times. Simple arithmetic.

The real win: you do it in one pass. No counting, no second traversal, no reloading nodes from cold cache. In production, that translates directly to fewer microseconds per request. When your list is chaining through a high-throughput pipeline, those microseconds compound into saved dollars.

Edge cases? Null head returns null. Single node returns the same node. The algorithm naturally handles both — no special-case checks needed.

// io.thecodeforge — dsa tutorial

public class FastSlowMiddle {
    static class Node {
        int data;
        Node next;
        Node(int data) { this.data = data; }
    }

    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;
            fast = fast.next.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        Node head = new Node(10);
        head.next = new Node(20);
        head.next.next = new Node(30);
        head.next.next.next = new Node(40);
        head.next.next.next.next = new Node(50);
        head.next.next.next.next.next = new Node(60);
        System.out.println("Middle: " + findMiddle(head).data);
    }
}

The Real Middle Problem: Concurrency and Mutability

Here's what no tutorial tells you: finding the middle of a linked list in a single-threaded vacuum is trivial. The moment you put this logic in a production service where other threads are concurrently inserting, deleting, or moving nodes, your "middle" becomes a moving target.

Imagine this: your fast pointer is two steps ahead, but a concurrent thread deletes the node it's about to land on. Now you're either dereferencing a stale pointer (segfault in native code) or reading garbage. Even with garbage collection, you can get corrupted data if the list structure mutates mid-traversal.

We solved this at my last gig by using immutable linked list versions — copy-on-write semantics for the critical path. If you can't afford that, at least guard with a read-write lock. And never, ever assume the list length is stable between two traversals. That naively counted length from pass one? It could be wrong by the start of pass two.

Bottom line: the algorithm is correct in math. In a real system, correctness depends on your memory model and locking strategy. Don't forget that.

// io.thecodeforge — dsa tutorial

import java.util.concurrent.locks.ReentrantReadWriteLock;

public class ConcurrentMiddle {
    static class Node {
        int data;
        volatile Node next;
        Node(int data) { this.data = data; }
    }

    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();

    public Node findMiddleSafe(Node head) {
        lock.readLock().lock();
        try {
            if (head == null) return null;
            Node slow = head;
            Node fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        } finally {
            lock.readLock().unlock();
        }
    }
}