Reverse List in Pairs
Mahabharata — The Twin Swap — Trading Every Two Warriors in the Column
युग्मेन युग्मं परिवर्तयेत् — प्रत्येकौ स्थानं विनिमयेताम्। पंक्तिः नूतना — युगलानां विनिमयेन सिध्यति॥
*Swap pair by pair — let each two exchange their positions. The new column emerges — perfected through the exchange of pairs.*
The Story
Given a linked list, swap every two adjacent nodes and return the head. You must NOT modify values; only the node links can be changed.
`1→2→3→4` becomes `2→1→4→3`
Nakula and Sahadeva always fought as a pair. General Yudhishthira ordered: "For each pair of warriors, let the second lead the first."
**Recursive approach (elegant):** - Base case: 0 or 1 node → return as-is - Take the second node as the new head for this pair - Recursively swap the rest (starting from third node) - Connect: second.next = first, first.next = recursive_result
```java if (head == null || head.next == null) return head; ListNode second = head.next; ListNode next = second.next; second.next = head; head.next = swapPairs(next); return second; ```
Trace for `1→2→3→4`: - swapPairs(1): second=2, next=3. Recurse: swapPairs(3) - swapPairs(3): second=4, next=null. Recurse: swapPairs(null)=null - 4.next=3, 3.next=null. Return 4. - Back at 1: 2.next=1, 1.next=4. Return 2. Result: `2→1→4→3` ✓
**Iterative approach (O(1) space):** Use a dummy node. Maintain `prev` pointing to node before the pair. For each pair (first=prev.next, second=first.next): 1. first.next = second.next (skip over second) 2. second.next = first (second now points back to first) 3. prev.next = second (prev connects to second — new pair head) 4. prev = first (advance prev to end of swapped pair)
Both approaches are O(n). Recursive uses O(n) stack space; iterative is O(1).
The Value-Swapper's Instinct
Traverse the list, swapping values of adjacent pairs. O(n) time, but modifies values (which is disallowed per constraints).
public ListNode swapPairsBruteForce(ListNode head) {
ListNode curr = head;
while (curr != null && curr.next != null) {
int temp = curr.val;
curr.val = curr.next.val;
curr.next.val = temp;
curr = curr.next.next;
}
return head;
}Nakula's Pair-Swap Wisdom
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null && prev.next.next != null) {
ListNode first = prev.next;
ListNode second = first.next;
// Swap
first.next = second.next;
second.next = first;
prev.next = second;
// Advance
prev = first;
}
return dummy.next;
}Step-by-Step Walkthrough
1→2→3 (odd length) dummy→1→2→3, prev=dummy Iter1: first=1,second=2. 1→3. 2→1. dummy→2. prev=1. List: dummy→2→1→3. prev.next=1, prev.next.next=3 (only one more node) Iter2: prev.next.next=null → stop. Return 2→1→3 ✅ (last odd node stays)
Deep Insight
**Recursive vs iterative space:** - Recursive: O(n/2) stack frames = O(n) space - Iterative: O(1) space — preferred for large lists
**Why dummy node?** The first pair swap changes the head itself. The dummy node gives us a stable `prev.next = second` assignment even for the first pair.
**Relation to lr-4 (reverse k-group):** This is lr-4 with k=2. The k-group reversal is the generalization — lr-3 is a special case.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Value swap — but modifies values (constraint violation) |
| Optimal | O(n) | O(1) | Iterative link manipulation, single pass |
Pattern Recognition
✅ Swap adjacent pairs in linked list ✅ Dummy node + prev pointer for consistent relinking ✅ Three rewires per pair: first→skip, second→first, prev→second ✅ Special case of lr-4 with k=2 **LeetCode Trigger Phrases:** → "swap nodes in pairs" → "swap every two adjacent nodes" → Without modifying node values
Bhagavad Gita 7.27
द्वन्द्वानि भरतश्रेष्ठ द्वन्द्वमोहेन भारत। सर्वभूतानि सम्मोहं सर्गे यान्ति परन्तप॥
O best of Bharatas, all beings fall into delusion at birth through the pairs of opposites arising from desire and aversion, O Parantapa.
Connection: The universe operates in pairs — day and night, joy and sorrow, first and second. The pair-swap algorithm embodies this cosmic duality: each pair exchanges positions, the second becoming first and the first becoming second. Like the Gita's teaching on transcending the pairs of opposites, the algorithm treats each duality as a single unit of transformation, swapping with precision and moving on.