Reorder List
Reorder List is a medium linked list problem solved with the slow fast pointers pattern.
The best approach, optimal (middle + reverse + merge), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from array of nodes + two pointers up.
Problem
You are given the head of a singly linked list whose nodes, in order, are L0, L1, L2, …, Ln-1, Ln. Rearrange the list in place so the nodes appear as L0, Ln, L1, Ln-1, L2, Ln-2, …: the first node, then the last, then the second, then the second to last, and so on.
Move the nodes by changing their next pointers; do not change the values stored in them. The function returns nothing — the list starting at head is checked after the call.
Examples
Example 1
- Input
head = [10, 20, 30, 40, 50]- Output
[10, 50, 20, 40, 30]- Why
- Take the first node, then the last, then the second, then the second to last, and finish with the middle node 30.
Example 2
- Input
head = [7, 3, 9, 1]- Output
[7, 1, 3, 9]- Why
- With an even length the front and back halves alternate until they meet: 7, 1, then 3, 9.
Example 3
- Input
head = [6]- Output
[6]- Why
- A single node is already in the required order.
Constraints
- The list has
1to5 * 10^4nodes. 1 <= Node.val <= 1000- Rearrange the nodes themselves; do not just overwrite their values.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Array of nodes + two pointers | O(n) | O(n) |
| Optimal (middle + reverse + merge) | O(n) | O(1) |
1Array of nodes + two pointers
O(n)One pass to fill the array and one pass to relink.O(n)The array holds a reference to every node.Copy every node reference into an array so you can jump to the back in O(1). Then relink the nodes by taking one from the left end and one from the right end alternately.
- Walk the list and store each node in an array.
- Set i = 0 and j = n - 1.
- While i < j: link nodes[i] -> nodes[j], move i forward; if i == j stop, otherwise link nodes[j] -> nodes[i] and move j back.
- The node at position i is now the tail: set its next to null.
class Solution {
public void reorderList(ListNode head) {
List<ListNode> nodes = new ArrayList<>();
for (ListNode cur = head; cur != null; cur = cur.next) nodes.add(cur);
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:
def reorderList(self, head: Optional[ListNode]) -> None:
nodes = []
cur = head
while cur:
nodes.append(cur)
cur = cur.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 = Noneclass Solution {
public:
void reorderList(ListNode* head) {
vector<ListNode*> nodes;
for (ListNode* cur = head; cur != nullptr; cur = cur->next) nodes.push_back(cur);
int i = 0, j = (int)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 = nullptr;
}
};function reorderList(head) {
const nodes = [];
for (let cur = head; cur !== null; cur = cur.next) nodes.push(cur);
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;
}2Optimal (middle + reverse + merge)
O(n)Finding the middle, reversing and merging each touch every node at most once.O(1)Only a handful of pointers; the nodes are relinked in place.Split the job into three classic list moves. Use slow and fast pointers to find the end of the first half, cut the list there, reverse the second half in place, then interleave: one node from the first half, one from the reversed second half, and so on.
- slow = head, fast = head; while fast.next and fast.next.next exist, move slow one step and fast two steps. slow is the end of the first half.
- second = slow.next; slow.next = null to cut the list.
- Reverse second with the prev / cur / next loop.
- Weave: while second is not null, save both next pointers, link first -> second -> first.next, then advance both.
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode prev = null, cur = slow.next;
slow.next = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
ListNode first = head, second = prev;
while (second != null) {
ListNode n1 = first.next, n2 = second.next;
first.next = second;
second.next = n1;
first = n1;
second = n2;
}
}
}class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
if head is None or head.next is None:
return
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
prev, cur = None, slow.next
slow.next = None
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
first, second = head, prev
while second:
n1, n2 = first.next, second.next
first.next = second
second.next = n1
first, second = n1, n2class Solution {
public:
void reorderList(ListNode* head) {
if (head == nullptr || head->next == nullptr) return;
ListNode* slow = head;
ListNode* fast = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* prev = nullptr;
ListNode* cur = slow->next;
slow->next = nullptr;
while (cur != nullptr) {
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
ListNode* first = head;
ListNode* second = prev;
while (second != nullptr) {
ListNode* n1 = first->next;
ListNode* n2 = second->next;
first->next = second;
second->next = n1;
first = n1;
second = n2;
}
}
};function reorderList(head) {
if (head === null || head.next === null) return;
let slow = head, fast = head;
while (fast.next !== null && fast.next.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
let prev = null, cur = slow.next;
slow.next = null;
while (cur !== null) {
const next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
let first = head, second = prev;
while (second !== null) {
const n1 = first.next, n2 = second.next;
first.next = second;
second.next = n1;
first = n1;
second = n2;
}
}Edge cases to test
- One or two nodes: nothing moves
- Odd length: the middle node ends up last
- Even length: the last two nodes of the result are the two middle nodes
- Duplicate values (nodes are what move, not values)
Hints
Hint 1
The output alternates between the front of the list and the back of the list. What makes the back hard to reach in a singly linked list?
Hint 2
If the second half were reversed, both halves could be walked forward at the same time.
Hint 3
Find the middle with slow and fast pointers, reverse the second half in place, then weave the two halves together.
FAQ
What is the best time complexity for Reorder List?
Optimal (middle + reverse + merge) runs in O(n) time and O(1) extra space. Finding the middle, reversing and merging each touch every node at most once.
Which pattern does Reorder List use?
It is a linked list problem that uses the slow fast pointers pattern. Other problems with the same pattern: Middle of the Linked List, Linked List Cycle, Linked List Cycle II.
Is there a brute force solution for Reorder List?
Yes. Array of nodes + two pointers takes O(n) time and O(n) space. Copy every node reference into an array so you can jump to the back in O(1).
Which edge cases should I test for Reorder List?
One or two nodes: nothing moves; Odd length: the middle node ends up last; Even length: the last two nodes of the result are the two middle nodes; Duplicate values (nodes are what move, not values).