Definition
- Reorder pattern – interleave a list with itself from both ends: first, last, second, second-last, and so on.
- Phase 1 – find the middle with fast-slow pointers and split into front and back halves.
- Phase 2 – reverse the back half in place.
- Phase 3 – merge the two halves by alternating one node from front, one from reversed back.
- Constraint – node values cannot change; only node links may be rearranged.
- Complexity – O(n) time, O(1) extra space.
At the National Bank of India, the risk team processes a queue of loan applications numbered 1 to n and wants to pair the earliest with the latest, then the second with the second-last. A clerk finds the middle of the queue, turns the back half around, then zips the two halves together: front, back, front, back.
Understanding the Concepts
What is the problem?
Given a singly linked list L0 -> L1 -> ... -> Ln, reorder it to L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> .... You may not change node values, only rearrange the nodes.
At the National Bank of India, the risk team wants to interleave fresh and aged loan applications for balanced review.
How does the three-phase approach work?
package com.bank.service;
public class ReorderList {
public static void reorder(ListNode head) {
if (head == null || head.next == null) return;
// Phase 1: Find middle and split
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode second = slow.next;
slow.next = null; // split
// Phase 2: Reverse second half
ListNode prev = null, curr = second;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
second = prev;
// Phase 3: Alternating merge
ListNode first = head;
while (second != null) {
ListNode firstNext = first.next;
ListNode secondNext = second.next;
first.next = second;
second.next = firstNext;
first = firstNext;
second = secondNext;
}
}
public static void main(String[] args) {
// Build: 1 -> 2 -> 3 -> 4 -> 5
ListNode head = new ListNode(1,
new ListNode(2, new ListNode(3,
new ListNode(4, new ListNode(5)))));
reorder(head);
// Print: 1 -> 5 -> 2 -> 4 -> 3
ListNode curr = head;
while (curr != null) {
System.out.print(curr.val + (curr.next != null ? " -> " : "\n"));
curr = curr.next;
}
}
}
1 -> 5 -> 2 -> 4 -> 3
Why save both next pointers in the merge phase?
When you set first.next = second, the original first.next is lost. When you set second.next = firstNext, the original second.next is lost. Save both before overwriting.
// Wrong: loses the chain
first.next = second; // first's original next is gone
second.next = first.next; // this is now 'second' itself!
// Correct: save first
ListNode firstNext = first.next;
ListNode secondNext = second.next;
first.next = second;
second.next = firstNext;
first = firstNext;
second = secondNext;
How does the split work for odd and even lengths?
The loop condition fast.next != null && fast.next.next != null ensures the front half is never shorter than the back half.
- Even `[1,2,3,4]`: front = `[1,2]`, back = `[3,4]`. After reverse: back = `[4,3]`. Merge: `1->4->2->3`. - Odd `[1,2,3,4,5]`: front = `[1,2,3]`, back = `[4,5]`. After reverse: back = `[5,4]`. Merge: `1->5->2->4->3`.
The merge terminates when the (shorter or equal) back half runs out.
What is the time and space complexity?
| Phase | Time | Space |
|---|---|---|
| Find middle | O(n) | O(1) |
| Reverse | O(n/2) | O(1) |
| Merge | O(n/2) | O(1) |
| Total | O(n) | O(1) |
What are common mistakes?
Using the wrong loop condition for finding the middle, which can make the front half shorter than the back half, causing the merge to leave dangling nodes.
// Wrong: fast can overshoot, making front shorter
while (fast != null && fast.next != null) { ... }
// For [1,2,3,4]: front=[1,2,3], back=[4] -- unbalanced
// Correct for reorder: use fast.next checks
while (fast.next != null && fast.next.next != null) { ... }
// For [1,2,3,4]: front=[1,2], back=[3,4] -- balanced
What are the edge cases?
- **Empty list**: nothing to do. - **Single node**: nothing to do. - **Two nodes**: `1->2` becomes `1->2` (already correct). - **Three nodes**: `1->2->3` becomes `1->3->2`.
What should a senior engineer know?
This problem composes three well-known subroutines. In an interview, demonstrating that you recognize and reuse building blocks shows stronger engineering than writing everything from scratch.
The constraint that values cannot be changed forces physical node relinking, which tests pointer manipulation skills specifically.
What are common interview follow-up questions?
- What if you could use extra space? (Copy into array, rearrange with two pointers, done.)
- How would you do this with a doubly linked list? (Use two pointers from both ends, no reversal needed.)
- Can you generalize to interleave k lists? (Merge k lists in round-robin.)
Visual Overview
List: 1 -> 2 -> 3 -> 4 -> 5
Phase 1: Find middle, split
Front: 1 -> 2 -> 3
Back: 4 -> 5
Phase 2: Reverse back half
Back: 5 -> 4
Phase 3: Alternating merge
first=1, second=5
1 -> 5 -> 2 (first moves to 2, second moves to 4)
2 -> 4 -> 3 (first moves to 3, second is null)
Stop.
Result: 1 -> 5 -> 2 -> 4 -> 3
┌──────────────────────────────────────────────┐ │ Reorder List Flow │ ├──────────────────────────────────────────────┤ │ │ │ Phase 1: Find middle with fast/slow │ │ Split into front + back │ │ │ │ │ ▼ │ │ Phase 2: Reverse back half │ │ │ │ │ ▼ │ │ Phase 3: Alternating merge │ │ ┌──────────────────────────────┐ │ │ │ While back is not null: │ │ │ │ save first.next, second.next│ │ │ │ first -> second -> firstNext│ │ │ │ advance both pointers │ │ │ └──────────────────────────────┘ │ │ │ │ Result: L0 -> Ln -> L1 -> Ln-1 -> ... │ └──────────────────────────────────────────────┘
Key Takeaway
Reordering a linked list into the front-back interleaved pattern is a three-phase in-place algorithm. Find the middle and split, reverse the back half, then alternate one node from the front with one from the reversed back. The whole thing runs in O(n) time with O(1) space.
The merge phase is the trickiest part because you must save each node's next pointer before overwriting it. Losing the chain mid-merge is the most common bug.
At the National Bank of India, the risk team processed a daily queue of loan applications and wanted them reordered so each review pass paired the earliest with the latest. The queue was a singly linked list, and this three-phase algorithm produced the front-and-back interleaving in place.
The correctness detail is the split: by using fast.next != null && fast.next.next != null, the front half is never shorter than the back half, so the merge terminates cleanly on both odd and even lengths.
Remember one sentence: split at the middle, reverse the back half, and zip the two halves together node by node.
---