Middle of the Linked List
The key idea
Move two pointers from the head:
slow one node at a time, fast two nodes at a time. When fast runs off the end, slow sits exactly in the middle. For an even-length list this lands on the second of the two middle nodes.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.
Constraints
- The number of nodes in the list is in the range
[1, 100]. 1 <= Node.val <= 100
Examples
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization