Reorder List

Take a singly linked list L0 → L1 → … → Ln - 1 → Ln and rearrange its nodes so they alternate between the front and the back, changing only the links and never the values:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

Example: 1->2->3->4 becomes 1->4->2->3.

We can put all nodes into a Deque (Double Ended Queue). Then, we can pop from the front and back alternately to build the new list.

• Drawback: Uses O(N) extra space to store all node references.

We need access to the end of the list, but we only have a forward pointer. Does this remind you of Palindrome check? We needed to access the end there too.

1. Find Middle: Split the list into two halves.
2. Reverse Second Half: The second half starts at slow.next. For 1->2->3->4, slow stops at 3, so the halves are 1->2->3 and 4; for 1->2->3->4->5 they are 1->2->3 and 4->5, reversed to 5->4.
3. Merge: Pick one from first, then one from second. 1 -> 4 -> 2 -> 3.

Watch the three steps as structure: the cut at slow.next = NULL turns one row into two, flipping the second half makes that row read backward, and each splice links a node from the lower row into the upper one until a single row remains.