Reorder List
MediumLinked lists
You get the head of a singly linked list whose nodes, in order, are L0, L1, …, Ln. Rearrange its nodes into the order L0, Ln, L1, Ln-1, L2, Ln-2, …: first, last, second, second to last, and so on.
Change the list in place by moving nodes, not by changing their values. The function returns nothing; the test reads the list again from the same head. On this page a list is written as an array of its values, from head to tail.
Examples
Input: head = [10, 20, 30, 40, 50] Output: [10, 50, 20, 40, 30]
First, last, second, second to last, and the middle node 30 ends the list.
Input: head = [1, 2, 3, 4] Output: [1, 4, 2, 3]
4 moves in after 1, and 3 stays after 2.
Constraints
- The list has 1 to 5 × 10⁴ nodes.
-1000 ≤ node.val ≤ 1000
Stuck?
Hint 1
The second half of the list, read backwards, is exactly the order the inserted nodes come in.
Hint 2
Find the middle with a slow and a fast pointer, cut the list there, reverse the second half, then weave the two halves together one node from each.
The idea
The nodes that get slotted in between, read in order, are the second half of the list backwards. So the job is three list moves: find the middle, reverse the second half, then weave the two halves together one node from each.
Time O(n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 6
A list of zero or one node is already in order. Stopping here also keeps the pointer code below from reading next off null.
function reorderList(head) { if (!head || !head.next) return; let slow = head; let fast = head; while (fast.next && fast.next.next) { slow = slow.next; fast = fast.next.next; } let second = slow.next; slow.next = null; let previous = null; while (second) { const next = second.next; second.next = previous; previous = second; second = next; } let first = head; second = previous; while (second) { const firstNext = first.next; const secondNext = second.next; first.next = second; second.next = firstNext; first = firstNext; second = secondNext; }}The trap
Finding the middle, cutting and weaving are all right, but the second half is woven in front to back instead of back to front. On lists of three nodes or fewer the second half has one node, so its order cannot be wrong and the answer looks fine. From four nodes on, the nodes slotted in come in the wrong order.
function reorderList(head) { if (!head || !head.next) return; let slow = head; let fast = head; while (fast.next && fast.next.next) { slow = slow.next; fast = fast.next.next; } let second = slow.next; // never reversed, so the back half comes in the wrong order slow.next = null; let first = head; while (second) { const firstNext = first.next; const secondNext = second.next; first.next = second; second.next = firstNext; first = firstNext; second = secondNext; }}