Reorder List
MediumSplit, reverse the tail, interleave
Problem
Given the head of a singly linked list L0 -> L1 -> ... -> Ln, reorder it to L0 -> Ln -> L1 -> Ln-1 -> ... without changing node values, only rewiring pointers.
Split in half, reverse the back half, then zip the two halves alternately.
The idea
Three known routines composed: find the middle, reverse the second half, then weave the two halves together alternating nodes. Each step is a pattern you already have; the problem is recognising the composition.
The trick
- Terminate the first half before reversing, or the weave loops forever.
- Stop weaving when the second half runs out.
- O(n) time, O(1) space.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — head = [1, 2, 3, 4] Values: 1, 2, 3, 4.
1mid = middle(head)2second = reverse(mid)3// alternately splice nodes from first and second halves4merge alternate(head, second)Input
- array
- [1, 2, 3, 4]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- list = 1 -> 2 -> 3 -> 4
- Output:
- 1 -> 4 -> 2 -> 3
- Explanation:
- Weave first and last: 1,4,2,3.
Example 2
- Input:
- list = 1 -> 2 -> 3 -> 4 -> 5
- Output:
- 1 -> 5 -> 2 -> 4 -> 3
- Explanation:
- 1,5,2,4,3.
Example 3
- Input:
- list = 1
- Output:
- 1
- Explanation:
- Single node.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.