Midpoint of the Chain
EasyLinked ListFree
Problem
A playlist is stored as a singly linked list. The shuffle feature wants to start playback from the middle track.
Given the head of the list, return the middle node (the list from that node to the end). When the list has an even number of nodes there are two middles: return the second one.
Example 1
- Input:
- head = [1, 2, 3, 4, 5]
- Output:
- [3, 4, 5]
Five nodes: the third one, value 3, is the middle.
Example 2
- Input:
- head = [1, 2, 3, 4, 5, 6]
- Output:
- [4, 5, 6]
Six nodes: the middles are 3 and 4, and the second one is returned.
Constraints
- 1 ≤ number of nodes ≤ 10^4
- -10^5 ≤ node.val ≤ 10^5
- Aim for one pass and O(1) extra space.
Hint
Show the first hint
Counting the nodes first and then walking half way works. Can you do it while walking only once?
Walkthrough
How to approach it
01Clarify before coding
- Which middle for an even length? The second one, so [1, 2, 3, 4] returns [3, 4].
- Can the list be empty? No, there is at least one node.
- Should I return a value or the node? The node: the harness reads the list from it to the end.
02Brute force
Walk the list once to count n, then walk again n // 2 steps from the head.
Cost: O(n) time and O(1) space, but two passes. It is a correct answer; the interviewer will ask for a single pass.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.