Because a linked list has no length field and no indices, even "go to the middle" needs a traversal. One classic approach uses two pointers moving at different speeds.
Given the head of a singly linked list, return the middle node. If there are two middle nodes (even length), return the second one. Return the node itself, not its value; the tests convert the rest of the list from that node onward.
Examples
Input: 1 -> 2 -> 3 -> 4 -> 5
Output: the node 3 (so the list from it reads 3 -> 4 -> 5)
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6
Output: the node 4 (the second of the two middle nodes)
Constraints
1 <= number of nodes <= 1000
Goals
- Find the length of a linked list by traversal
- Apply the fast and slow pointer technique to locate the middle in one pass