How Do You Find the Middle of a Linked List?
Learn the slow-fast pointer technique to find a linked list’s middle node in one pass, with code and interview tips.
Expected Interview Answer
You find the middle of a linked list in a single pass using the slow-fast pointer technique: advance a slow pointer one node at a time and a fast pointer two nodes at a time, and when the fast pointer reaches the end, the slow pointer is at the middle, achieving O(n) time and O(1) space without first counting the list’s length.
Because the fast pointer always covers exactly twice the distance of the slow pointer in the same number of steps, the slow pointer is guaranteed to be positioned at the halfway point the instant the fast pointer runs out of nodes. For an odd-length list this lands exactly on the single middle node, while for an even-length list the convention (checking fast versus fast.next) determines whether you land on the first or second of the two middle nodes. The naive alternative walks the list once to count nodes, then walks it again to index into the middle, which is also O(n) time but requires two passes instead of one. This technique underlies problems like finding the middle to split a list for merge sort, or to check if a list is a palindrome.
- Single pass, O(n) time
- O(1) space, no counting array needed
- Naturally extends to splitting a list in half
- Same pointer pattern as cycle detection, easy to remember together
AI Mentor Explanation
To find the midpoint of a boundary rope without measuring it first, send two fielders jogging from one end, one at normal pace and one at double pace. When the faster fielder reaches the far end of the rope, the slower fielder is standing exactly at the halfway mark, since the faster one always covers twice the ground in the same time. No one needs to first walk the whole rope with a tape measure to know where the middle is.
Step-by-Step Explanation
Step 1
Initialize both pointers at head
Set slow = head and fast = head before the loop begins.
Step 2
Advance at a 1:2 ratio
Each iteration, move slow one node and fast two nodes.
Step 3
Stop when fast runs out
Loop while fast and fast.next are both non-null.
Step 4
Read the middle from slow
When the loop ends, slow points to the middle node (or the second middle for even-length lists).
What Interviewer Expects
- Explain the 1:2 speed ratio and why it lands slow at the midpoint
- Correctly handle even-length lists and clarify which middle node is returned
- State O(n) time and O(1) space, contrasting with the two-pass counting approach
- Mention at least one use case, like splitting a list for merge sort
Common Mistakes
- Off-by-one errors on even-length lists, landing on the wrong middle node
- Forgetting to check fast.next before dereferencing fast.next.next
- Doing two passes (count then index) when one pass suffices
- Not handling an empty list or single-node list as edge cases
Best Answer (HR Friendly)
“I use two pointers starting together, one moving one step and one moving two steps at a time. By the time the faster pointer reaches the end, the slower one is naturally sitting at the middle, so I find the midpoint in a single pass without ever counting the list first.”
Code Example
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def middle_node(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slowFollow-up Questions
- How would you adjust this to return the first middle node on an even-length list instead of the second?
- How would you use this technique to split a list into two halves for merge sort?
- How would you check if a linked list is a palindrome using this middle-finding step?
- What happens if the list is empty when you call this function?
MCQ Practice
1. When the fast pointer reaches the end of the list, where does the slow pointer end up?
Because fast always moves twice as far as slow in the same number of steps, slow lands at the midpoint when fast finishes.
2. What is the time complexity of this middle-finding approach?
It requires a single traversal of the list, giving O(n) time.
3. Compared to counting the list length first and then indexing, the two-pointer approach is preferred because it:
The two-pointer technique finds the middle in one pass, while counting-then-indexing requires two passes.
Flash Cards
What pointer pattern finds the middle of a linked list in one pass? — Slow and fast pointers, where slow moves one node and fast moves two nodes per step.
What is the time and space complexity of this technique? — O(n) time, O(1) space.
Where does the slow pointer end up when fast reaches the end? — Exactly at the middle node of the list.
Name one classic use case for finding the middle of a linked list. — Splitting a list in half for merge sort, or checking for a palindrome.