Lesson 77 of 250
143. Reorder List
NeetCode: Reorder List · LeetCode: 143. Reorder List · Difficulty: Medium
Reorder L0 -> L1 -> ... -> Ln into L0 -> Ln -> L1 -> Ln-1 -> L2 -> ... by changing links, without a new list.
Example
Input: 2 -> 4 -> 6 -> 8 Output: 2 -> 8 -> 4 -> 6
Input: 2 -> 4 -> 6 -> 8 -> 10 Output: 2 -> 10 -> 4 -> 8 -> 6Java linked structures use null and mutable fields, so the list is a chain of ListNode objects, the end is next == null, and the empty list is null. The helper fromArray builds a list from its values and toList copies a list into an ArrayList for printing.
Brute force: read into an ArrayList, write back in the new order
Collect the values, build the interleaved order using two indices from both ends, and write it back over the list. LeetCode's method is void and changes the list in place, so the result is read from the same head.
import java.util.ArrayList;
import java.util.List;
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
class Solution {
public void reorderList(ListNode head) {
List<Integer> values = new ArrayList<>();
for (ListNode cur = head; cur != null; cur = cur.next) {
values.add(cur.val);
}
int lo = 0;
int hi = values.size();
List<Integer> order = new ArrayList<>();
while (lo < hi) {
order.add(values.get(lo));
lo++;
if (lo < hi) {
hi--;
order.add(values.get(hi));
}
}
ListNode cur = head;
for (int v : order) {
cur.val = v;
cur = cur.next;
}
}
}
public class Main {
static ListNode fromArray(int... values) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
for (int v : values) {
tail.next = new ListNode(v);
tail = tail.next;
}
return dummy.next;
}
static List<Integer> toList(ListNode head) {
List<Integer> out = new ArrayList<>();
for (ListNode cur = head; cur != null; cur = cur.next) {
out.add(cur.val);
}
return out;
}
public static void main(String[] args) {
Solution s = new Solution();
ListNode a = fromArray(2, 4, 6, 8);
s.reorderList(a);
System.out.println(toList(a));
ListNode b = fromArray(2, 4, 6, 8, 10);
s.reorderList(b);
System.out.println(toList(b));
}
}[2, 8, 4, 6]
[2, 10, 4, 8, 6]Time: O(n). Space: O(n). This rewrites values rather than links, which the problem forbids in its strict form.
Optimal: find the middle, reverse the second half, merge
- Split. Count the length; the first half keeps
(len + 1) / 2nodes, so walk(len - 1) / 2steps from the head and set the last first-half node'snexttonull, keeping the rest as the second half. - Reverse the second half.
- Merge by alternating one node from each half onto a dummy node's tail.
Example 2 -> 4 -> 6 -> 8 -> 10: first half 2 -> 4 -> 6, second half reversed 10 -> 8, merged 2, 10, 4, 8, 6. The first half is never shorter than the second, so it supplies the last node when len is odd.
import java.util.ArrayList;
import java.util.List;
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
class Solution {
public void reorderList(ListNode head) {
int len = 0;
for (ListNode p = head; p != null; p = p.next) {
len++;
}
if (len < 3) {
return;
}
// 1. split after the last node of the first half
ListNode cur = head;
for (int i = 0; i < (len - 1) / 2; i++) {
cur = cur.next;
}
ListNode second = cur.next;
cur.next = null; // cut, otherwise the merged list would contain a cycle
// 2. reverse the second half
ListNode rev = null;
while (second != null) {
ListNode next = second.next;
second.next = rev;
rev = second;
second = next;
}
// 3. merge: one node from each half in turn
ListNode first = head;
while (rev != null) {
ListNode firstNext = first.next;
ListNode revNext = rev.next;
first.next = rev;
rev.next = firstNext;
first = firstNext;
rev = revNext;
}
}
}
public class Main {
static ListNode fromArray(int... values) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
for (int v : values) {
tail.next = new ListNode(v);
tail = tail.next;
}
return dummy.next;
}
static List<Integer> toList(ListNode head) {
List<Integer> out = new ArrayList<>();
for (ListNode cur = head; cur != null; cur = cur.next) {
out.add(cur.val);
}
return out;
}
public static void main(String[] args) {
Solution s = new Solution();
ListNode a = fromArray(2, 4, 6, 8);
s.reorderList(a);
System.out.println(toList(a));
ListNode b = fromArray(2, 4, 6, 8, 10);
s.reorderList(b);
System.out.println(toList(b));
}
}[2, 8, 4, 6]
[2, 10, 4, 8, 6]The merge loop runs while the reversed half has nodes. The first half has the same length or one more, so first is never null inside the loop, and the last first-half node already ends with next == null.
Time: O(n). Space: O(1) extra: links are rewired, no node is copied.
How to explain it in an interview
- Say first: "Dump values into a list and write them back in the order first, last, second, second-last:
O(n)time and space, and it rewrites values, not links." - Key insight: the new order is "first half interleaved with the reversed second half", and each of those is a standard list operation.
- Code it in steps: (1) count and cut after
(len - 1) / 2steps by settingnext = null; (2) reverse the second half; (3) merge, alternating nodes of the two halves. - Complexity to state:
O(n)time,O(1)extra space. - Likely follow-ups / pitfalls: odd versus even length (first half gets the extra node); forgetting to cut the first half, which leaves a cycle; lists of length 0 to 2 are already in order.