Linked List · LC #876
Middle of the Linked List
Find the middle node of a singly linked list in one pass using the fast/slow pointer technique. For even-length lists, returns the second middle node.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
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.
Sample I/O
Input: 1→2→3→4→5 Output: node 3 (value 3) Input: 1→2→3→4→5→6 Output: node 4 (second middle)
Intuition
How to Think About It
Intuition
If a fast pointer moves at twice the speed of a slow pointer, when the fast pointer reaches the end the slow pointer is exactly at the midpoint. This avoids the need to count the length first. The behavior for even-length lists (returning the second middle) falls out naturally from the termination condition.
Core Concept
Initialise slow = fast = head. Each iteration: slow = slow.next, fast = fast.next.next. Loop while fast != null && fast.next != null. When the loop exits, slow is the middle node. For odd-length lists fast ends exactly at the tail; for even-length lists fast goes past the tail, leaving slow at the second of the two midpoints. Time: O(n), Space: O(1).
When to use
Finding the midpoint in one pass; prerequisite step for Reorder List, Merge Sort on Linked List, and Palindrome Linked List.
When NOT to use
When the list length is known - just advance n/2 steps. When you need the first middle for even-length lists - adjust the loop condition to `fast.next != null && fast.next.next != null`.
Key Insights
What to Know Cold
- Termination condition fast != null && fast.next != null prevents null-pointer exceptions on even-length lists.
- For even-length lists, the slow pointer lands on the second middle - this matches LC #876's requirement.
- To get the first middle instead, change loop condition to: while (fast.next && fast.next.next).
- This is the first step in three-step Reorder List: find middle → reverse second half → interleave.
- Also used in finding the middle for bottom-up merge sort on linked lists.
1 example
Worked Examples
Even-length list - second middle
1→2→3→4→5→6
Fast/slow pointer
function middleNode(head: ListNode | null): ListNode | null {
let slow = head, fast = head;
while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; }
return slow;
}Output: Node with value 4
Single-pass O(n) midpoint - critical building block for Reorder List and Palindrome Linked List.