Middle of the Linked List
Understanding the Problem
Finding the middle of a list sounds trivial, but two properties of a singly linked list complicate it.
First, we don't know the length upfront. There's no .length property and no random access. We can only traverse node by node from the head. Finding the middle therefore means either counting the nodes first or tracking position during a single traversal.
Second, the even-length case has two candidates. For a list with 6 nodes, the two middle positions are index 2 and index 3 (0-indexed). The problem asks for the second one, index 3. This determines exactly where the traversal must stop.
The question that drives the optimal solution: can we find the middle in a single pass, without knowing the length in advance?
Key Constraints:
Number of nodes in range [1, 100]→ The input is small, so even an O(n) approach with extra space runs instantly. The technique below still matters because it scales to any list length.n >= 1→ The list is never empty, so we don't need a special case for a null head. The first node always exists.
Approach 1: Convert to Array
Intuition
A linked list has no random access, but an array does. So copy every node reference into an array, then index straight to the middle. For an array of size n, the index n / 2 (integer division) is the middle. For even n it gives the higher of the two middle indices, which is the second middle node the problem asks for.
This costs O(n) extra space, but indexing into the array replaces any reasoning about where a traversal should stop.
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.
The array is the only reason this uses O(n) space. The next approach removes it by traversing the list twice instead of storing it.
Approach 2: Two-Pass (Count then Traverse)
Intuition
To avoid the array, traverse the list twice. The first pass counts the total number of nodes, n. The second pass walks exactly n / 2 steps from the head to reach the middle node.
This replaces the array with a single integer counter and a pointer, so the extra space drops to O(1).
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.
Two passes still traverse the list twice. The next approach reaches the middle in a single pass by moving two pointers at different speeds.
Approach 3: Slow and Fast Pointers
Intuition
Use two pointers that move at different speeds in a single pass. The slow pointer advances one node at a time. The fast pointer advances two nodes at a time. By the time fast reaches the end of the list (or moves past it), slow has reached the middle.
After each iteration slow has moved half as far as fast. So whenever fast sits at index 2k, slow sits at index k. The loop runs while fast can still take a full two-step move.
For odd n, fast stops on the last node (index n-1), giving slow index (n-1)/2, the single middle. For even n, fast steps past the end to null, having reached index n, giving slow index n/2, the second of the two middles. Both match the index n / 2 the array approach computes.
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.