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.

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.

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.

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.

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.

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.

Frequently Asked Questions