Reorder List — Split, Reverse, Merge
Break the list in half, reverse the back half, and weave the two lists together to match L0, Ln, L1, Ln-1 ... order.
Problem Statement
Given the head of a singly linked list, reorder the list so that nodes alternate from the front and back without creating new nodes.
Why This Problem Matters
- Combines multiple classic linked-list subroutines (find middle, reverse, merge) in one problem.
- Shows that complex transformations can be decomposed into reusable primitives.
- Highlights in-place manipulation without extra allocations.
Thought Process
Find the midpoint
Use slow/fast pointers so the list can be split into two halves.
Reverse the second half
Reversing the tail positions nodes in the order we need to interleave.
Merge alternating nodes
Stitch one node from the front half, then one from the reversed half, stopping when the second half ends.
Step-by-Step Reasoning
- Handle short lists up front.
- Locate the middle node and split the list.
- Reverse the second half starting at the middle.
- Merge the two lists by alternating pointers until the second half is exhausted.
Dry Run
List = 1→2→3→4→5
Middle = 3, reversed tail = 5→4→3, merge yields 1→5→2→4→3.
List = 1→2→3→4
Middle = 3, reversed tail = 4→3, merge outputs 1→4→2→3.
Complexity Analysis
Time
O(n)
Space
O(1)
Why
Each list pass (find mid, reverse, merge) is linear with constant extra storage.
Annotated Solution
public class ReorderList {
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
ListNode mid = middle(head);
ListNode second = reverse(mid);
merge(head, second);
}
private ListNode middle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
private void merge(ListNode first, ListNode second) {
while (second.next != null) {
ListNode tmp1 = first.next;
ListNode tmp2 = second.next;
first.next = second;
second.next = tmp1;
first = tmp1;
second = tmp2;
}
}
public static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
}Three linear passes—find middle, reverse second half, merge alternately—reorder the list without extra space.
Common Pitfalls
- Failing to break the list before reversing can create a cycle.
- Stopping the merge when l1 becomes null leaves leftover nodes from the second half.
- Incorrect pointer updates can lose nodes; store next pointers before rewiring.
Follow-Up Questions
- Modify the algorithm to support doubly linked lists.
- What changes if you must keep relative ordering when nodes hold equal values?