Reorder List
MediumThe problem
Given the head of a linked list L0 → L1 → L2 → ... → Ln, rearrange it in place so it becomes L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ... (first, last, second, second last, and so on). Rewire the nodes' next pointers rather than changing their values. The function returns nothing; head ends up as the reordered list.
- Example 1Input: head = [1, 2, 3, 4]Output: [1, 4, 2, 3]
First 1, then the last 4, then 2, then the last remaining 3.
- Example 2Input: head = [1, 2, 3, 4, 5]Output: [1, 5, 2, 4, 3]
First 1, last 5, then 2, last remaining 4, and 3 is left in the middle.
- 1 ≤ number of nodes ≤ 50,000
- 1 ≤ node value ≤ 1,000
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
The result alternates front, back, front, back. Which three smaller problems combine to do that?
The idea
Find the middle (slow/fast), reverse the second half, then interleave the two halves node by node.
Target: O(n) time, O(1) space
Go function shape
func reorderList(head *ListNode)Reference solution
Tested with go test. Try it yourself first, then compare.
// ReorderList turns L0→L1→…→Ln into L0→Ln→L1→Ln-1→… in place, in three small steps:
// find the middle, reverse the second half, then weave the two halves together.
func ReorderList(head *ListNode) {
if head == nil || head.Next == nil {
return
}
slow, fast := head, head.Next // fast starts one ahead so slow stops at the END of the first half
for fast != nil && fast.Next != nil {
slow, fast = slow.Next, fast.Next.Next
}
second := slow.Next
slow.Next = nil // cut the list in two
var prev *ListNode
for second != nil {
second.Next, prev, second = prev, second, second.Next // reverse the second half
}
first, second := head, prev
for second != nil {
fNext, sNext := first.Next, second.Next
first.Next = second
second.Next = fNext
first, second = fNext, sNext
}
}