You get the head of a singly linked list with nodes L0 → L1 → … → Ln-1. Rearrange it so that it alternates between the front and the back, working inwards from both ends:
L0 → Ln-1 → L1 → Ln-2 → L2 → Ln-3 → …
Relink the nodes themselves rather than rewriting the values stored in them. Return nothing: the answer is the list read from head once your function finishes.
The first node stays first, the last node comes second, the second node third, the second-to-last fourth, and so on until the two ends meet in the middle.
With an odd number of nodes, the middle node 4 is the one left over, and it ends the list.
A single node is already in order.
Constraints
n nodes, where 1 <= n <= 5 * 10⁴.1 <= Node.val <= 1000The answer weaves the first half with the second half read backwards. A singly linked list can't be walked backwards, but you can reverse half of it.
Write the answer out for six nodes, L0 → L5 → L1 → L4 → L2 → L3, and read only every other node. The odd places hold L0, L1, L2, the front half in order. The even places hold L5, L4, L3, the back half backwards. So the task is to weave two lists together, taking one node from each in turn.
Time O(n)Space O(1)
The full walkthrough and code are part of Premium