Questions
5 of 16
How do you find the middle of a Linked List in one pass?
Difficulty: 2/10
Finding the Middle Node
The standard one-pass solution uses slow and fast pointers. Slow advances one node at a time while fast advances two. When fast reaches the end, slow is positioned at the middle.
javascript
- 1
Time complexity: O(n).
- 2
Auxiliary space: O(1).
- 3
For an odd-length list, slow identifies the unique middle.
- 4
For an even-length list, this initialization returns the second middle node.
- 5
The choice of first or second middle can be changed by adjusting the pointer initialization or loop condition.
Follow-up Questions
- How do you return the first middle for an even-length list?
- Can this technique be used for cycle detection?