Middle of the Linked List
Last Updated: March 29, 2026
Understanding the Problem
At first, this seems straightforward: find the middle of a list and return it. But there are a couple of things worth thinking about.
First, in a singly linked list, we don't know the length upfront. There's no .length property or random access. We have to traverse node by node from the head. So finding the "middle" requires us to either count first or use a clever traversal trick.
Second, the even-length case matters. For a list with 6 nodes, there are two candidates for the middle: nodes at index 2 and index 3 (0-indexed). The problem says to return the second one, which is index 3. This detail affects where our pointer needs to land.
The key question is: can we find the middle in a single pass without knowing the length in advance?
Key Constraints:
Number of nodes in range [1, 100]→ Very small input. Even O(n^2) would be instant. But the real goal is to learn the technique, which scales to any size.1 <= Node.val <= 100→ Values are positive integers. This doesn't affect the algorithm but simplifies debugging.n >= 1→ The list is never empty. We don't need to handle the null head case.
Approach 1: Convert to Array
Intuition
The simplest way to deal with the "no random access" limitation of linked lists: just convert it to an array. Once we have an array, finding the middle is trivial. The middle index of an array of size n is n / 2 (integer division), and this conveniently gives us the second middle for even-length lists.
This approach uses extra space, but it makes the logic dead simple and is a good starting point.
Algorithm
- Traverse the linked list, storing each node in an array.
- Find the middle index:
mid = array.length / 2. - Return the node at
array[mid].
Example Walkthrough
Code
- Time Complexity: O(n). We traverse the entire list once to collect all nodes, then do a constant-time array lookup.
- Space Complexity: O(n). We store all n nodes in an array.
This approach works but uses extra space. Can we find the middle without storing all nodes?
Approach 2: Two-Pass (Count then Traverse)
Intuition
If we don't want to use extra space, we can take two passes through the list. The first pass counts the total number of nodes. The second pass walks exactly n / 2 steps from the head to land on the middle node.
This eliminates the array entirely. We only need an integer counter and a pointer.
Algorithm
- Traverse the entire list to count the total number of nodes
n. - Calculate the middle index:
mid = n / 2. - Traverse the list again from the head, advancing
midsteps. - Return the node we land on.
Example Walkthrough
Code
- Time Complexity: O(n). Two passes through the list: one full traversal (n steps) and one partial traversal (n/2 steps). Total is O(n + n/2) = O(n).
- Space Complexity: O(1). Only a counter variable and a pointer. No additional data structures.
This works but requires two passes. What if two pointers could work together in a single pass to find the middle?
Approach 3: Slow and Fast Pointers
Intuition
This is the classic technique for finding the middle of a linked list in a single pass. The idea is simple but elegant: use two pointers, one moving at twice the speed of the other.
The slow pointer advances one node at a time. The fast pointer advances two nodes at a time. When fast reaches the end of the list (or goes past it), slow is exactly at the middle.
Because slow has covered half the distance that fast has. If fast has traversed the entire list (n nodes), slow has traversed n/2 nodes, which is the middle. For even-length lists, when fast goes past the end (becomes null), slow is at the second middle node, which is exactly what the problem wants.
Algorithm
- Initialize
slow = headandfast = head. - While
fastis not null andfast.nextis not null, advanceslowby one step andfastby two steps. - When the loop ends,
slowis the middle node. Return it.
Example Walkthrough
Code
- Time Complexity: O(n). The fast pointer traverses roughly n/2 iterations, visiting n nodes total (2 steps per iteration). Overall it's O(n).
- Space Complexity: O(1). Only two pointer variables. No additional data structures.