39. Swap Nodes in Pairs
mediumAsked at OlaSwap every two adjacent nodes of a linked list.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Given a linked list, swap every two adjacent nodes and return its head. You must do the problem without modifying the values in the list's nodes (only nodes themselves may be changed).
Constraints
Number of nodes is in [0, 100]0 <= Node.val <= 100
Examples
Example 1
Input
head = [1,2,3,4]Output
[2,1,4,3]Example 2
Input
head = []Output
[]Approaches
1. Collect then rebuild
Read values into an array, swap pairs, then walk and update nodes.
- Time
- O(n)
- Space
- O(n)
const arr = []; let n = head;
while (n) { arr.push(n.val); n = n.next; }
for (let i=0;i+1<arr.length;i+=2) [arr[i],arr[i+1]] = [arr[i+1],arr[i]];
n = head; let k = 0;
while (n) { n.val = arr[k++]; n = n.next; }
return head;Tradeoff:
2. Pointer relink
Walk with a prev pointer; relink each pair in place. O(n) and O(1) space.
- Time
- O(n)
- Space
- O(1)
function swapPairs(head) {
const dummy = { next: head };
let prev = dummy;
while (prev.next && prev.next.next) {
const a = prev.next, b = a.next;
a.next = b.next;
b.next = a;
prev.next = b;
prev = a;
}
return dummy.next;
}Tradeoff:
Ola-specific tips
Ola interviewers want to see pointer hygiene without value swap; tie it to reordering a chain of dispatch handoffs without losing references.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.