293. Middle Link
A relay race is run along a chain of checkpoints, each pointing to the next. The organiser wants a medal handed out at the middle checkpoint, but nobody has counted the checkpoints and counting twice would waste time.
Given the head of the chain, return the middle node itself (the node object that is in the chain, not a copy). When the chain has an even number of nodes there are two middle nodes; return the second one. The chain has at least one node. Try to solve it with a single pass over the chain.
Example 1
- Input:
- head = [14,23,37,41,58]
- Output:
- 2
- Explanation:
Five nodes: the middle one holds 37.
Example 2
- Input:
- head = [8,15,16,23]
- Output:
- 2
- Explanation:
Four nodes: the two middle nodes are 15 and 16, and the second one, 16, is returned.
Constraints
1 ≤ chain length ≤ 105
-1000 ≤ node value ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)