Reorder List
Problem Statement
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 → … 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
Input Format:
- The head of a singly linked list
Output Format:
- Reorder the list in-place according to the pattern described
Examples:
Example 1:
Input:
head = [1,2,3,4]
Output:
[1,4,2,3]
Explanation:
The list has been reordered from 1→2→3→4 to 1→4→2→3.
Example 2:
Input:
head = [1,2,3,4,5]
Output:
[1,5,2,4,3]
Explanation:
The list has been reordered from 1→2→3→4→5 to 1→5→2→4→3.
Solutions
Three-Step Approach: Find Middle, Reverse Second Half, Merge
Find the middle of the linked list, reverse the second half, and then merge the two halves alternately.
Using a Stack Approach
Use a stack to store the second half of the linked list nodes and then rearrange them.
Algorithm Walkthrough
Example input: nums = []
Step-by-step execution:
- Initial list: 1 -> 2 -> 3 -> 4
- Step 1: Find the middle. slow = node with value 2, fast = node with value 4
- Step 2: Reverse second half. Reversed second half: 4 -> 3 -> null
- Break the list: First half: 1 -> 2 -> null, Second half: 4 -> 3 -> null
- Step 3: Merge alternately:
- First iteration: 1 -> 4 -> 2 -> null, remaining second: 3 -> null
- Second iteration: 1 -> 4 -> 2 -> 3 -> null, remaining second: null
- Final reordered list: 1 -> 4 -> 2 -> 3 -> null
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize finding the middle, reversing the second half, and merging the two halves alternately.
Key visualization elements:
- middle finding
- reversing
- merging
Implementation Notes
This problem tests understanding of linked list manipulations, finding the middle of a list, and in-place reversal. The three-step approach is memory efficient and elegant.