Swap Nodes in Pairs — Solution in Python, Java & C++
Swap Nodes in Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on recursion.
Swap Nodes in Pairs is a medium coding problem on recursion, asked in Amazon, Microsoft, Meta and Bloomberg interviews.
- Difficulty: Medium
- Topics: Recursion
- Asked at: Amazon, Microsoft, Meta, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the head of a singly linked list, swap every two adjacent nodes — the 1st with the 2nd, the 3rd with the 4th, and so on — and return the head of the new list. A last node without a partner stays where it is.
Change the links, not the values: the nodes themselves must move.
Example 1
Input: head = [1,2,3,4]
Output: [2,1,4,3]
Example 2
Input: head = []
Output: []
Example 3
Input: head = [1,2,3]
Output: [2,1,3]
Explanation: Node 3 has no partner and keeps its place.
Constraints
The number of nodes in the list is in the range [0, 100]0 <= Node.val <= 100
Hints for Swap Nodes in Pairs
Hint 1
Work on one pair at a time: the pair
(a, b)that follows some nodeprevbecomes(b, a).Hint 2
Three links change per pair:
prev.next = b,a.next = b.next,b.next = a.Hint 3
Then
ais the node before the next pair. A dummy node before the head playsprevfor the first pair.
How to solve Swap Nodes in Pairs
Walk the list pair by pair, keeping the node before each pair. Swapping a pair is three link changes, and the first node of the old pair ends up as the predecessor of the next one.
Approach
- Create a dummy node pointing at
head; setprev = dummy. - While
prev.nextandprev.next.nextexist: leta = prev.next,b = a.next. - Relink:
a.next = b.next,b.next = a,prev.next = b. - Move on with
prev = a. - Return
dummy.next.
Why it works
Each iteration turns prev → a → b → rest into prev → b → a → rest, touching nothing else, and leaves prev before rest. The loop stops when fewer than two nodes remain, which leaves an odd last node untouched.
Complexity
- Time —
O(n) - Space —
O(1) iteratively (the recursive version uses O(n) stack)
Pitfalls
- Order the three assignments so no link is lost: save
b.next(viaa.next = b.next) before overwritingb.next. - Swapping values instead of nodes defeats the exercise.
- Both the empty list and a single node must come back unchanged.
Reference solution
Python
from typing import Optional
def swapPairs(head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head)
prev = dummy
while prev.next and prev.next.next:
a = prev.next
b = a.next
a.next = b.next
b.next = a
prev.next = b
prev = a
return dummy.nextJava
public static ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0, head), prev = dummy;
while (prev.next != null && prev.next.next != null) {
ListNode a = prev.next, b = a.next;
a.next = b.next;
b.next = a;
prev.next = b;
prev = a;
}
return dummy.next;
}C++
ListNode* swapPairs(ListNode* head) {
ListNode dummy(0, head);
ListNode* prev = &dummy;
while (prev->next && prev->next->next) {
ListNode* a = prev->next;
ListNode* b = a->next;
a->next = b->next;
b->next = a;
prev->next = b;
prev = a;
}
return dummy.next;
}JavaScript
var swapPairs = function(head) {
var dummy = new ListNode(0, head), prev = dummy;
while (prev.next !== null && prev.next.next !== null) {
var a = prev.next, b = a.next;
a.next = b.next;
b.next = a;
prev.next = b;
prev = a;
}
return dummy.next;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 40 recursion problems · the whole catalogue
Learn the technique: Recursion