Middle of the Linked List
Find the middle node in one pass using the speed-1 / speed-2 pointer pair.
2 min read
fast-slow linked-list
Problem#
Given the head of a singly linked list, return the middle node. For even-length lists, return the second of the two middles.
Examples#
[1,2,3,4,5]→ node3[1,2,3,4,5,6]→ node4
Constraints#
- List length in
[1, 100].
Approach#
slow advances one step, fast advances two. When fast reaches the end, slow is at the middle.
Solution#
class Solution {public: ListNode* middleNode(ListNode* head) { ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; }};func middleNode(head *ListNode) *ListNode { slow, fast := head, head for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next } return slow}from typing import Optional
class Solution: def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slowfunction middleNode(head) { let slow = head, fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } return slow;}class Solution { public ListNode middleNode(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; }}function middleNode(head: ListNode | null): ListNode | null { let slow: ListNode | null = head, fast: ListNode | null = head; while (fast && fast.next) { slow = (slow as ListNode).next; fast = fast.next.next; } return slow;}Editorial#
For even-length n, fast lands on nullptr after n/2 iterations and slow is at index n/2 (the second middle). For odd n, fast lands on the last node and slow is at index (n-1)/2. No length precomputation needed — the speed ratio carries the bookkeeping.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#