Middle of the Linked List
Problem
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 number of nodes in the list is in the range [1, 100]
- 1 ≤ Node.val ≤ 100
Example
head = [1,2,3,4,5][3,4,5]The linked list has 5 nodes. The middle node is the 3rd node with value 3. The algorithm uses two pointers: 'slow' moves one step at a time, 'fast' moves two steps. When 'fast' reaches the end, 'slow' is at the middle. Here, 'slow' points to node with value 3, which is returned.
Approach
Straightforward Solution
A naive approach counts the total number of nodes in one pass, then traverses again to the middle node. This requires two passes and O(n) time.
Core Observation
The middle node is the node at position floor(n/2) + 1 in a 1-indexed list. Using two pointers moving at different speeds allows locating this node in a single pass without knowing the list length upfront.
Path to Optimal
The key insight is to use two pointers: 'fast' moves twice as fast as 'slow'. When 'fast' reaches the end, 'slow' will be at the middle. This eliminates the need for two passes and finds the middle in one traversal.
Optimal Approach
Initialize two pointers at the head. Move 'slow' one step and 'fast' two steps in each iteration. When 'fast' is null or 'fast.next' is null, 'slow' points to the middle node. Return 'slow'.
Time
O(n)
Each pointer traverses the list at most once. The 'fast' pointer moves two nodes per iteration, so the loop runs approximately n/2 times.
Space
O(1)
Only two pointers are used regardless of input size, so the auxiliary space is constant.
Pattern Spotlight
Fast & Slow Pointers (Tortoise and Hare)
Use two pointers moving at different speeds to detect midpoints or cycles in linked structures; the slower pointer's position when the faster pointer reaches the end reveals key structural information.
Solution
| 1 | class Solution: |
| 2 | def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]: |
| 3 | |
| 4 | slow = head |
| 5 | fast = head |
| 6 | |
| 7 | while fast and fast.next: |
| 8 | slow = slow.next |
| 9 | fast = fast.next.next |
| 10 | |
| 11 | return slow |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public ListNode middleNode(ListNode head) { |
| 5 | ListNode slow = head; |
| 6 | ListNode fast = head; |
| 7 | |
| 8 | while (fast != null && fast.next != null) { |
| 9 | slow = slow.next; |
| 10 | fast = fast.next.next; |
| 11 | } |
| 12 | |
| 13 | return slow; |
| 14 | } |
| 15 | } |
| 1 | #include <iostream> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | public: |
| 7 | ListNode* middleNode(ListNode* head) { |
| 8 | ListNode* slow = head; |
| 9 | ListNode* fast = head; |
| 10 | |
| 11 | while (fast != nullptr && fast->next != nullptr) { |
| 12 | slow = slow->next; |
| 13 | fast = fast->next->next; |
| 14 | } |
| 15 | |
| 16 | return slow; |
| 17 | } |
| 18 | }; |
| 1 | var middleNode = function(head) { |
| 2 | let slow = head; |
| 3 | let fast = head; |
| 4 | |
| 5 | while (fast !== null && fast.next !== null) { |
| 6 | slow = slow.next; |
| 7 | fast = fast.next.next; |
| 8 | } |
| 9 | |
| 10 | return slow; |
| 11 | }; |
Step-by-Step Solution
Initialize Slow and Fast Pointers at the Head
| 4 | slow = head |
| 5 | fast = head |
Objective
To set up two pointers starting at the head of the linked list to begin traversal.
Key Insight
Starting both pointers at the head ensures they traverse the list in sync, with the fast pointer moving twice as fast. This setup is essential for the two-pointer technique to correctly identify the middle node in one pass.
Interview Quick-Check
Core Logic
Both pointers start at the head to maintain relative positions; the fast pointer's double speed relative to slow is the core mechanism.
State & Boundaries
Initializing both pointers at the head handles edge cases like single-node lists naturally.
Advance Slow by One and Fast by Two Until Fast Reaches End
| 7 | while fast and fast.next: |
| 8 | slow = slow.next |
| 9 | fast = fast.next.next |
Objective
To traverse the list with two pointers moving at different speeds until the fast pointer reaches the end.
Key Insight
Moving the fast pointer two steps and the slow pointer one step per iteration ensures that when the fast pointer reaches the end, the slow pointer is at the middle. The loop condition checks both 'fast' and 'fast.next' to avoid null pointer exceptions and to handle even-length lists correctly.
Interview Quick-Check
Core Logic
The loop condition 'while fast and fast.next' ensures safe traversal and correct termination when the fast pointer reaches the list's end.
Common Pitfalls & Bugs
Failing to check 'fast.next' can cause runtime errors when the list length is even.
State & Boundaries
The slow pointer moves one step per iteration, so when the loop ends, it points to the middle node.
Return the Slow Pointer as the Middle Node
| 11 | return slow |
Objective
To return the node currently pointed to by the slow pointer, which is the middle node of the list.
Key Insight
After the loop terminates, the slow pointer is guaranteed to be at the middle node due to the relative speeds of the pointers. Returning slow satisfies the problem requirement, including the case where there are two middle nodes (returns the second).
Interview Quick-Check
Core Logic
Returning the slow pointer after traversal yields the middle node as per the two-pointer traversal logic.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
return slowReturn the slow pointer as the middle node.
Returning slow here is the definitive step that solves the problem; it leverages the invariant that slow is at the middle when fast reaches the end, making this line the core of the solution.
while fast and fast.next:Continue looping while fast and fast.next are not null.
This loop condition is critical to safely advance the fast pointer two steps without causing runtime errors, and it ensures the slow pointer stops exactly at the middle node.
slow = slow.nextMove the slow pointer one step forward.
Advancing slow by one step per iteration ensures it progresses at half the speed of fast, positioning it at the middle when fast reaches the end.
fast = fast.next.nextMove the fast pointer two steps forward.
Advancing fast by two steps per iteration makes it traverse the list twice as fast as slow, enabling the two-pointer technique to find the middle node in a single pass.
slow = headInitialize the slow pointer to the head of the list.
Starting slow at the head ensures it begins traversal from the first node, maintaining the correct relative position to fast.
fast = headInitialize the fast pointer to the head of the list.
Starting fast at the head allows it to move twice as fast as slow, enabling the two-pointer technique to find the middle node in one pass.
Test Your Understanding
Why does moving one pointer twice as fast as the other guarantee that the slower pointer will be at the middle when the faster pointer reaches the end?
Because the fast pointer covers twice the distance of the slow pointer, when the fast pointer reaches the end (or null), the slow pointer must have covered half the distance, placing it exactly at the middle node.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct Middle of the Linked List from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Middle of the Linked List drill