DSA problem
Middle of the Linked List
Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes (i.e., the list has an even number of nodes), return the second middle node.
The naive way to solve this is in two passes. First walk the entire list once to count the total number of nodes n; then walk again n / 2 steps from the head to land on the middle. That is O(n) time but it scans the list twice — wasteful when the list is huge or stored on slow memory.
The elegant single-pass technique is the classic fast and slow pointer pattern. Both pointers start at the head; the slow pointer advances one step per iteration while the fast pointer advances two steps. Because fast moves at exactly twice the speed of slow, by the time fast walks off the end of the list, slow has covered only half of it — which is precisely the middle.
For a list of odd length, fast lands on the last node and slow lands on the single middle. For a list of even length, fast falls off the end after the last node and slow lands on the second of the two middles, which is exactly what the problem requires. The whole algorithm finishes in one O(n) pass with O(1) extra space.
Examples
head = [1,2,3,4,5][3,4,5]head = [1,2,3,4,5,6][4,5,6]head = [1][1]Constraints
- The number of nodes in the list is in the range [1, 100].
- 1 <= Node.val <= 100
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.