Reorder List
You get the head of a singly linked list with nodes L0, L1, L2, ..., Ln in that order. Reorder it into L0, Ln, L1, Ln-1, L2, Ln-2, and so on: the first node, then the last, then the second, then the second to last.
Change the order of the existing nodes rather than the values inside them (the tests only check the final order). Return the head of the reordered list. For example 1, 2, 3, 4 becomes 1, 4, 2, 3, and 1, 2, 3, 4, 5 becomes 1, 5, 2, 4, 3.
Examples
Input head = [1, 2, 3, 4]
Output [1, 4, 2, 3]
Input head = [1, 2, 3, 4, 5]
Output [1, 5, 2, 4, 3]
Input head = [1]
Output [1]
Constraints
- 1 <= number of nodes <= 500
- 1 <= node value <= 1,000
Stuck? Take one hint at a time
Common mistakes
- Forgetting to cut the list after the middle, so the first half still points into the second half and the result contains a cycle.
- Weaving the halves without saving both next pointers first, which loses the rest of each half.
- Changing only the values of the nodes instead of relinking them.
- Getting the middle wrong for even lengths, which puts one node in the wrong half and breaks the order.
Questions an interviewer may ask next
- Why does the three step version test fast.next and fast.next.next rather than fast and fast.next? (For an even length it stops on the first of the two middle nodes, so the halves are equal. The other test stops on the second middle node and gives the first half one extra node.)
- Check whether a linked list is a palindrome in O(1) memory. (Middle, reverse, compare.)
- Reorder a doubly linked list. Which step gets simpler?
- Reorder the list in blocks of k nodes.
head
[1,2,3,4]
Expected output
[1,4,2,3]
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.