Reorder List
Understanding the Problem
We need to rearrange a singly linked list so that nodes alternate between the front and the back. Take the first node, then the last node, then the second node, then the second-to-last node, and so on. The difficulty is that this is a singly linked list, so we cannot traverse backward to reach those "back" nodes cheaply.
The reordered list is the first half of the original interleaved with its second half reversed. For [1, 2, 3, 4, 5], that means interleaving the first half [1, 2, 3] with the reversed second half [5, 4] to get 1 -> 5 -> 2 -> 4 -> 3. Every approach below relies on this structure. They differ only in how they reach the back nodes: by copying references into an array, or by reversing the second half in place.
Key Constraints:
- Up to
5 * 10^4nodes. An O(n^2) approach, such as repeatedly scanning to the tail to find the last unplaced node, would run up to 2.5 billion operations and time out. An O(n) solution is required. - The list is singly linked, so we cannot walk backward. Any approach that needs the back nodes must either copy node references into a random-access structure or reverse part of the list in place.
- Values are fixed (
1 <= Node.val <= 1000) and must not be modified. We rearrange the nodes themselves, never their values, so the value range does not affect the approach.
Approach 1: Using an Array
Intuition
The difficulty with a singly linked list is the lack of backward movement. Storing every node reference in an array removes that restriction: an array gives O(1) access to any position, including the last. With all nodes in an array, two pointers, one at the front and one at the back, can rewire the next connections directly in the required interleaved order.
This spends O(n) extra space to avoid any pointer reversal. It is the more direct of the two approaches and a useful baseline before the in-place version.
Algorithm
- Traverse the linked list and store each node reference in an array.
- Initialize two pointers:
left = 0andright = n - 1(where n is the number of nodes). - While
left < right: - Set
nodes[left].next = nodes[right](connect front node to back node). - Advance
leftby 1. - If
left == right, break (we've met in the middle). - Set
nodes[right].next = nodes[left](connect back node to the next front node). - Decrement
rightby 1. - Set the last node's
nexttonullto terminate the list.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We traverse the list once to store nodes in the array, then do one pass with two pointers to rewire. Both are O(n).
- Space Complexity: O(n). We store all n node references in an array.
The array stores every node, so this uses O(n) extra space. The next approach reaches the back nodes by reversing the second half in place, which removes the array and drops the space to O(1).
Approach 2: Find Middle + Reverse + Merge
Intuition
The reordered list is the first half interleaved with the reversed second half, and all three pieces can be done in place with constant extra space:
- Find the middle of the list, which splits it into two halves.
- Reverse the second half.
- Merge the two halves by alternating nodes.
Finding the middle uses two pointers at different speeds: slow moves one node per step, fast moves two. When fast can no longer advance two nodes, slow sits at the end of the first half. We then reverse everything after slow and alternate nodes from the two halves.
The way slow/fast advance leaves the first half with ceil(n/2) nodes and the reversed second half with floor(n/2) nodes, so the first half is always the same length as the second or exactly one node longer. The merge loop pulls one node from each half per iteration and stops when the second half is exhausted. Because the first half is never shorter, the leftover first-half node (present only when n is odd) is already the last node and keeps its original next, which the disconnection step set to null. No node is dropped or visited twice.
Algorithm
- Use slow and fast pointers to find the middle of the list. After this,
slowpoints to the end of the first half. - Reverse the second half of the list starting from
slow.next. Use the standard iterative reversal (prev/curr/next pointers). - Disconnect the first half from the second half by setting
slow.next = null. - Merge the two halves: take one node from the first half, then one from the second half, alternating until both lists are exhausted.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Finding the middle takes O(n/2), reversing the second half takes O(n/2), and merging takes O(n/2). Total: O(n).
- Space Complexity: O(1). We only use a constant number of pointer variables. No additional data structures.