Weave the front with the back
Reorder a list as first, last, second, second-last and so on, by combining three moves you already know - find the middle, reverse the back half and weave. About 18 minutes.
Three moves
The target order is the first node, then the last, then the second, then the second-last, and so on. Taking the last node of a single chain over and over is slow, since you must walk to it each time.
So change the shape of the problem. Cut the list in the middle, reverse the second half so that its last node leads, and weave the two halves together. The first half may be one node longer than the second.
second = slow.next slow.next = None # the first half ends
The middle is node 4. The first half is 2, 7, 4 and the second half is 9, 1, 6.
Cut, reverse, weave
After finding the middle, set the middle node's next to nothing. This ends the first half. The node after it starts the second half, which you reverse.
To weave, keep two pointers, one on each half. Save both next links, point the first node at the second, point the second at the saved first-half next, and move on. The loop runs while the second half has nodes.
a.next = b # a, then b, then the rest b.next = a_next
A list has 4 nodes: 1, 2, 3, 4. What is the reordered list?
- A1, 4, 2, 3
- B1, 3, 2, 4
- C4, 1, 3, 2
Show the answer
1, 4, 2, 3. First, last, second, second-last: 1, 4, 2, 3.
Reorder list
You get the head of a singly linked list. Reorder it so that it takes the first node, then the last, then the second, then the second to last, and so on, alternating between the front and the back. Return the head. Change the links only, never the values in the nodes.
head = [1, 2, 3, 4, 5] → [1, 5, 2, 4, 3]
0 ≤ number of nodes ≤ 5,000 · 1 ≤ node.val ≤ 1,000