Approach Summary
Three steps: find middle with slow/fast pointers, reverse the second half, merge two halves alternately.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Three-Phase In-Place Reordering (Optimal) | O(n) | O(1) | Find middle with slow/fast pointers, reverse second half, and interweave nodes in O(1) space. |
| 2 Approach 2: Array of Node Pointers Two-Pointer Reordering | O(n) | O(n) | Loads all node references into an indexed array, using two pointers from both ends to re-link nodes. |
Step 1: Baseline
Approach 1: Three-Phase In-Place Reordering (Optimal)
Time: O(n)
Space: O(1)
1) Tortoise and hare pointers locate the midpoint slow. 2) Sever the list after slow, then reverse the sublist starting at slow.next. 3) Two pointers p1 and p2 walk the first and reversed second half, splicing p2 between p1 and p1.next on each iteration.
Approach 1: Three-Phase In-Place Reordering (Optimal) Implementation
Approach 1: Three-Phase In-Place Reordering (Optimal)
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode prev = null, curr = slow.next;
slow.next = null;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
ListNode ptr1 = head, ptr2 = prev;
while (ptr2 != null) {
ListNode firstNext = ptr1.next;
ListNode secondNext = ptr2.next;
ptr1.next = ptr2;
ptr2.next = firstNext;
ptr1 = firstNext;
ptr2 = secondNext;
}
}
}class Solution {
public:
void reorderList(ListNode* head) {
if (!head || !head->next) return;
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* prev = NULL;
ListNode* curr = slow->next;
slow->next = NULL;
while (curr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
ListNode* ptr1 = head;
ListNode* ptr2 = prev;
while (ptr2) {
ListNode* firstNext = ptr1->next;
ListNode* secondNext = ptr2->next;
ptr1->next = ptr2;
ptr2->next = firstNext;
ptr1 = firstNext;
ptr2 = secondNext;
}
}
};class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
if not head or not head.next:
return
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
prev, curr = None, slow.next
slow.next = None
while curr:
curr.next, prev, curr = prev, curr, curr.next
p1, p2 = head, prev
while p2:
p1_nxt, p2_nxt = p1.next, p2.next
p1.next = p2
p2.next = p1_nxt
p1, p2 = p1_nxt, p2_nxtfunction reorderList(head) {
if (!head || !head.next) return;
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
let prev = null, curr = slow.next;
slow.next = null;
while (curr) {
const nxt = curr.next;
curr.next = prev;
prev = curr;
curr = nxt;
}
let p1 = head, p2 = prev;
while (p2) {
const n1 = p1.next, n2 = p2.next;
p1.next = p2;
p2.next = n1;
p1 = n1;
p2 = n2;
}
} Step 2: Most Optimized
Approach 2: Array of Node Pointers Two-Pointer Reordering
Time: O(n)
Space: O(n)
Traverses the list and stores all node pointers into an array. Uses two pointers i = 0 and j = n - 1: links nodes[i].next = nodes[j], then nodes[j].next = nodes[i + 1]. Terminates by setting the middle node next to null.
Approach 2: Array of Node Pointers Two-Pointer Reordering Implementation
Approach 2: Array of Node Pointers Two-Pointer Reordering
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
List<ListNode> nodes = new ArrayList<>();
ListNode curr = head;
while (curr != null) { nodes.add(curr); curr = curr.next; }
int i = 0, j = nodes.size() - 1;
while (i < j) {
nodes.get(i).next = nodes.get(j);
i++;
if (i >= j) break;
nodes.get(j).next = nodes.get(i);
j--;
}
nodes.get(i).next = null;
}
}class Solution {
public:
void reorderList(ListNode* head) {
if (!head || !head->next) return;
vector<ListNode*> nodes;
ListNode* curr = head;
while (curr) { nodes.push_back(curr); curr = curr->next; }
int i = 0, j = nodes.size() - 1;
while (i < j) {
nodes[i]->next = nodes[j];
i++;
if (i >= j) break;
nodes[j]->next = nodes[i];
j--;
}
nodes[i]->next = NULL;
}
};class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
if not head or not head.next: return
nodes = []
curr = head
while curr:
nodes.append(curr)
curr = curr.next
i, j = 0, len(nodes) - 1
while i < j:
nodes[i].next = nodes[j]
i += 1
if i >= j: break
nodes[j].next = nodes[i]
j -= 1
nodes[i].next = Nonefunction reorderList(head) {
if (!head || !head.next) return;
const nodes = [];
let curr = head;
while (curr) { nodes.push(curr); curr = curr.next; }
let i = 0, j = nodes.length - 1;
while (i < j) {
nodes[i].next = nodes[j];
i++;
if (i >= j) break;
nodes[j].next = nodes[i];
j--;
}
nodes[i].next = null;
}Edge Cases to Watch
- Empty list or single node list (e.g. head == null or head.next == null; returns immediately)
- Even number of nodes (e.g. 1 -> 2 -> 3 -> 4 becomes 1 -> 4 -> 2 -> 3)
- Odd number of nodes (e.g. 1 -> 2 -> 3 -> 4 -> 5 becomes 1 -> 5 -> 2 -> 4 -> 3)
- Two node list (1 -> 2 stays 1 -> 2)
Algorithmic Pattern
View Pattern Guide →
Master the Linked List Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Linked List pattern.
Framework: Linked List • Interview Prep: Tested at FAANG •
Explore all Linked List problems & invariants →
How to Recognize This Pattern
- Interleave first half with reversed second half
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
Linked List Two Pointers Stack
Frequently Asked Questions
What is the optimal time and space complexity for Reorder List?
The optimal solution for Reorder List achieves O(n) runtime complexity and requires O(1) auxiliary space. Time complexity is O(n) because finding the middle takes n/2 steps, reversing the second half takes n/2 steps, and merging takes n steps. Space complexity is O(1) as all transformations are performed purely by re-linking existing node pointers.
How do I identify that Reorder List requires the Linked List pattern?
In technical interviews, look for key problem signals: Interleave first half with reversed second half. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Linked List strategy.
What critical edge cases must be handled in Reorder List?
Essential edge cases to verify include: Empty list or single node list (e.g. head == null or head.next == null; returns immediately); Even number of nodes (e.g. 1 -> 2 -> 3 -> 4 becomes 1 -> 4 -> 2 -> 3); Odd number of nodes (e.g. 1 -> 2 -> 3 -> 4 -> 5 becomes 1 -> 5 -> 2 -> 4 -> 3); Two node list (1 -> 2 stays 1 -> 2). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Reorder List?
Reorder List is a Medium-difficulty question tagged with medium recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Facebook.