Rearrange a LinkedList
Mahabharata — Weaving the Pandava and Kaurava Armies — Alternating the First and Last Warriors
प्रथमश्च अन्तिमश्च मिलित्वा युद्धे चलन्ति। द्वितीयश्च पूर्वान्तिमः मध्ये तिष्ठन्ति वीरता॥
*First and last march together into battle; second and second-to-last stand in valor in the middle.*
The Story
On the eve of the Kurukshetra war, the great strategist Dhrishtadyumna devised an unprecedented formation for the Pandava army. Their warriors were arrayed in a line ordered by seniority: Yudhishthira (1), Bhima (2), Arjuna (3), Nakula (4), Sahadeva (5).
But the formation required a specific reordering: the warriors must be woven into an alternating pattern of first-and-last pairs. The new order must be: Yudhishthira (first), Sahadeva (last), Bhima (second), Nakula (second-to-last), Arjuna (middle).
The mathematical pattern: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...
"This weaving creates a pincer formation," Dhrishtadyumna explained. "The most experienced warrior (first) fights side by side with the most rear-positioned (last), creating mutual defense."
His aide Shikhandi asked: "How do we reorder a linked list of warriors this way without using extra scroll-space for a copy?"
"Three steps," Dhrishtadyumna replied, unrolling a battle map.
**Step 1: Find the middle.** Use fast & slow pointers. Split the list at the middle: first half [L0...Lm] and second half [Lm+1...Ln].
For [1,2,3,4,5]: Middle = 3. First half: [1,2,3]. Second half: [4,5].
**Step 2: Reverse the second half.** [4,5] becomes [5,4].
**Step 3: Merge them alternately.** Take one from first half, one from reversed second, repeat.
First: 1, 2, 3 Second (reversed): 5, 4
Merge: 1→5→2→4→3
Sahadeva (5) flanks Yudhishthira (1). Nakula (4) flanks Bhima (2). Arjuna (3) stands at center.
"The trick in the merge," Dhrishtadyumna continued, "is to update the .next pointers carefully. Take node from list1 (say `a`), take node from list2 (say `b`). Save the rest: `a_next = a.next`, `b_next = b.next`. Set `a.next = b`, `b.next = a_next`. Advance list1 = a_next, list2 = b_next."
Shikhandi traced through [1,2,3,4]:
Step 1: fast/slow → middle = node(2) Split: first=[1,2], second=[3,4]
Step 2: reverse second: [4,3]
Step 3 merge: - a=1, b=4. 1.next=4, 4.next=2. list1=2, list2=3 - a=2, b=3. 2.next=3, 3.next=null (list1 exhausted). Done. Result: 1→4→2→3 ✓
"Why split at the middle and reverse the second half?" Shikhandi asked. "Why not just walk from both ends simultaneously?"
"Because a linked list is singly linked — we cannot walk backwards," Dhrishtadyumna replied. "By reversing the second half, we convert the 'walking backward from the end' into 'walking forward from the new head of the reversed half'. This is a critical insight: reversal converts backward traversal into forward traversal."
The armies were woven. Yudhishthira and Sahadeva stood side by side on the left flank, Bhima and Nakula on the right, Arjuna in the center. The pincer formation deployed at dawn.
"This technique," Dhrishtadyumna said as war-drums began, "is used whenever you need to interleave the beginning and end of a sequence without using extra space. Find middle, reverse second half, merge alternately."
This is the Fast & Slow Pointer technique for rearranging a linked list.
Shikhandi's First Instinct
Collect all values in an ArrayList, then use two pointers (left, right) to weave them into a new list. O(n) space for the ArrayList.
public void reorderListBruteForce(ListNode head) {
if (head == null) return;
// Collect all nodes
List<ListNode> nodes = new ArrayList<>();
ListNode current = head;
while (current != null) {
nodes.add(current);
current = current.next;
}
// Weave using two pointers on the list
int left = 0, right = nodes.size() - 1;
while (left < right) {
nodes.get(left).next = nodes.get(right);
left++;
if (left == right) break;
nodes.get(right).next = nodes.get(left);
right--;
}
nodes.get(left).next = null; // Terminate the list
}Dhrishtadyumna's Wisdom
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
// Step 1: Find the middle
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow is now at the first middle node
// Step 2: Reverse the second half
ListNode secondHalf = reverseList(slow.next);
slow.next = null; // Cut the list in half
// Step 3: Merge the two halves alternately
ListNode first = head;
ListNode second = secondHalf;
while (second != null) {
ListNode firstNext = first.next;
ListNode secondNext = second.next;
first.next = second; // Insert second before firstNext
second.next = firstNext; // Continue with original first.next
first = firstNext; // Advance both pointers
second = secondNext;
}
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
// Test
public static void main(String[] args) {
// [1,2,3,4,5] → [1,5,2,4,3]
// [1,2,3,4] → [1,4,2,3]
}Step-by-Step Walkthrough
Input: 1 → 2 → 3 → 4 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ STEP 1 — Find middle Initial: slow=[1], fast=[1] Round 1: slow=[2], fast=[3] fast.next=[4], fast.next.next=null → STOP Middle = slow = [2] ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ STEP 2 — Split and reverse second half Second half starts at slow.next = [3] slow.next = null → First half: 1 → 2 → null Reverse [3→4→null]: becomes 4 → 3 → null secondHalf = [4] ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ STEP 3 — Merge alternately first=[1], second=[4] Iter 1: firstNext=[2], secondNext=[3] [1].next=[4], [4].next=[2] Now: 1→4→2... first=[2], second=[3] Iter 2: firstNext=null, secondNext=null [2].next=[3], [3].next=null Now: 1→4→2→3 first=null, second=null → DONE ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ ✅ Output: 1 → 4 → 2 → 3
Deep Insight
**Why use `fast.next != null && fast.next.next != null` instead of `fast != null && fast.next != null`?**
This variant ensures slow stops at the FIRST middle (not second), so the first half is the longer one for odd lists. This matters for the merge: the first half always has >= nodes as the second half, preventing issues when second half runs out before first.
**The merge step invariant:** At each step, we're inserting `second` between `first` and `first.next`. Saving both `firstNext` and `secondNext` before modifying `.next` pointers is critical — otherwise we lose our place.
**Edge cases:** - 1 node: function returns immediately - 2 nodes: middle=node1, second=[node2], merge gives node1→node2 (unchanged) - 3 nodes [1,2,3]: middle=[1], second=[3] (reversed [3]), merge: 1→3→2 ✓
**Odd vs even:** - Odd [1,2,3,4,5]: first=[1,2,3], second=[5,4], merge: 1→5→2→4→3 (middle goes to end) - Even [1,2,3,4]: first=[1,2], second=[4,3], merge: 1→4→2→3
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | ArrayList of all n nodes for index-based access |
| Optimal | O(n) | O(1) | Three in-place passes over the list |
Pattern Recognition
✅ Linked list reordering in a specific interleaved pattern ✅ Pattern: L0→Ln→L1→Ln-1→L2... ✅ O(1) space required (no ArrayList) ✅ Combination of: find middle + reverse + merge **LeetCode Trigger Phrases:** → "reorder list" + "L0→Ln→L1→Ln-1" → "in-place" + linked list reorder → "first and last alternately"
Bhagavad Gita 10.38
समो दण्डो दमयितुं साधूनां साधुता मम। मौनं चैवास्मि गुह्यानां ज्ञानं ज्ञानवतामहम्॥
I am the equal rod of justice for those who must be disciplined; I am the goodness of the good; I am the silence of secrets; I am the wisdom of the wise.
Connection: The reorder algorithm pairs the first with the last, the second with the second-to-last — like the divine principle of balance that Krishna describes, where strength and wisdom are distributed equally, the strong (first) paired with the experienced (last), the middle standing as the pivot of wisdom. The three-step algorithm achieves this cosmic reordering without disturbing the fundamental nature (values) of any node.