Reorder List

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

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: Now we have 1->2 and 4->3 (reversed).
3. Merge: Pick one from first, then one from second. 1 -> 4 -> 2 -> 3.

Visualize the three steps: Split, Reverse, and Merge.