Coding Interview PatternsMiddle of the Linked List
EasyFast and Slow Pointers
Middle of the Linked List
Explanation & Solution
Description
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
The result should be returned as the sublist from the middle node to the end of the list.
Input:head = [1,2,3,4,5]
0
1
1
2
2
3
3
4
4
5
Output:[3,4,5]
0
3
1
4
2
5
Explanation: The middle node of the list is node 3.
Constraints
- The number of nodes in the list is in the range
[1, 100] 1 <= Node.val <= 100
Approach
Fast and Slow Pointers pattern
1. Initialize Two Pointers
- Set
slowtohead - Set
fasttohead - Both pointers start at the beginning of the linked list
2. Traverse the List
- Loop while
fastis not null andfast.nextis not null - Move
slowforward by one step:slow = slow.next - Move
fastforward by two steps:fast = fast.next.next
3. Return the Middle
- When
fastreaches the end (or goes past it),slowis at the middle node - For odd-length lists,
slowis exactly at the center - For even-length lists,
slowis at the second of the two middle nodes - Collect all values from
slowto the end of the list into an array and return it
4. Why Does This Work?
- Since
fastmoves at twice the speed ofslow, whenfasthas traversed the entire list,slowhas traversed exactly half - This is a classic application of the fast-and-slow pointer (tortoise and hare) technique
Key Insight
- No need to count the length of the list first — the two-pointer approach finds the middle in a single pass
Time
O(n)we traverse the list onceSpace
O(1)only two pointer variables are used (excluding the output array)Visualization
Input:
Linked List Traversal
—
Press play to start traversal
Slow (S)Fast (F)Both
5 steps