Linked List · LC #143
Reorder List
Reorder a linked list into the interleaved pattern L0→Ln→L1→Ln-1→... in-place using three steps: find middle, reverse second half, merge two halves.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
You are given the head of a singly linked-list. The list can be represented as: L0 → L1 → … → Ln-1 → Ln. Reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … You may not modify the values in the list's nodes. Only nodes themselves may be changed.
Sample I/O
Input: 1→2→3→4 Output: 1→4→2→3 Input: 1→2→3→4→5 Output: 1→5→2→4→3
Intuition
How to Think About It
Intuition
The output alternates nodes from the front and back of the list. If you split the list at the midpoint and reverse the second half, you get two sequences that can be interleaved in order - exactly the desired output. This insight converts a "hard to see" pattern into three well-known sub-problems.
Core Concept
Step 1 - Find middle: use slow/fast pointers; slow.next = null severs the two halves. Step 2 - Reverse second half: standard iterative reversal on the second half. Step 3 - Merge/interleave: take one node from first half, one from reversed second half, alternating, until second half is exhausted. All three steps are O(n) time, O(1) space, totaling O(n)/O(1).
When to use
Any problem requiring interleaving a sequence with its reverse; also a pattern for palindrome checks that avoid extra space.
When NOT to use
When a copy of the list is acceptable - collect all nodes into an array and rebuild with index arithmetic. Simpler to code, O(n) extra space.
Key Insights
What to Know Cold
- Three distinct sub-problems (find mid, reverse, merge) each solved with known patterns - decomposition is the key insight.
- Must sever the list at the mid (slow.next = null) before reversing; otherwise the reversal overwrites the first half.
- Use the loop condition `fast.next && fast.next.next` (first-middle variant) so the first half is ≥ second half in length.
- Merge loop terminates on l2 being null (second half is shorter or equal); avoids out-of-bounds.
- Array approach (collect nodes, rebuild) is acceptable in interviews if O(n) space is allowed - mention trade-off.
1 example
Worked Examples
Reorder 5-node list
1→2→3→4→5 → 1→5→2→4→3
Find mid → reverse second half → interleave
function reorderList(head: ListNode | null): void {
let slow = head!, fast = head!;
while (fast.next && fast.next.next) { slow = slow.next!; fast = fast.next.next; }
// Reverse second half
let prev: ListNode | null = null, curr: ListNode | null = slow.next;
slow.next = null;
while (curr) { const next = curr.next; curr.next = prev; prev = curr; curr = next; }
// Interleave
let l1: ListNode | null = head, l2 = prev;
while (l2) { const n1 = l1!.next, n2 = l2.next; l1!.next = l2; l2.next = n1; l1 = n1; l2 = n2; }
}Output: 1→5→2→4→3
Combines three fundamental linked-list patterns - demonstrates ability to decompose and sequence sub-problems, a senior-level signal.