Reorder List

The key idea

Reordering L0->Ln->L1->Ln-1->... is just interleaving the list with its own reverse. Do it in O(1) space by splitting the list at the middle, reversing the second half in place, then weaving the two halves together node by node.

Problem

You are given the head of a singly linked list L0 -> L1 -> ... -> Ln-1 -> Ln.

Reorder the list to be in the following form:

L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Constraints

The number of nodes in the list is in the range [1, 5 * 10^4].
1 <= Node.val <= 1000

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]

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →