#24 Swap Nodes in Pairs
frequently reported atBloombergMicrosoftUberAmazonGoogleMeta
the problem
In plain words
Swap every two adjacent nodes of a linked list and return its head. You must move the nodes themselves, not change their values.
in head = [1,2,3,4]
out [2,1,4,3]
in head = [1,2,3]
out [2,1,3]
in head = []
out []
- 0 ≤ number of nodes ≤ 100
- 0 ≤ Node.val ≤ 100
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternIn-place linked-list rewiringRecursion on a smaller input
Handle only the first pair yourself. Everything after it is the same problem, two nodes shorter — let recursion swap it.
solutions
From brute force to optimal
Read values into a list, swap neighbours, build new nodes. Not allowed by the problem — a stepping stone only.
- Collect values.
- Swap indices (0,1), (2,3), ….
- Build a new list.
A few linear passes.
The value list and n new nodes.
class Solution { /** Swaps values via an array. LeetCode forbids changing values — shown only as a stepping stone. */ public ListNode swapPairs(ListNode head) { List<Integer> values = new ArrayList<>(); for (ListNode n = head; n != null; n = n.next) values.add(n.val); for (int i = 0; i + 1 < values.size(); i += 2) Collections.swap(values, i, i + 1); ListNode dummy = new ListNode(0), tail = dummy; for (int v : values) { tail.next = new ListNode(v); tail = tail.next; } return dummy.next; }}second becomes the new head; first.next = swapPairs(rest); second.next = first.
- Base case: 0 or 1 node.
- second = head.next.
- head.next = swapPairs(second.next).
- second.next = head; return second.
One call per pair.
n / 2 stack frames.
class Solution { public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) return head; // 0 or 1 node: nothing to swap ListNode second = head.next; head.next = swapPairs(second.next); // the rest of the list, already swapped second.next = head; // second now comes first return second; }}prev sits before each pair; rewire three pointers per pair.
- dummy → head, prev = dummy.
- first = prev.next, second = first.next.
- first.next = second.next; second.next = first; prev.next = second.
- prev = first.
One pass.
A few pointers.
class Solution { 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, second = first.next; first.next = second.next; // first skips over second second.next = first; // second points back to first prev.next = second; // the node before the pair points to second prev = first; // first is now the last node of this pair } return dummy.next; }}in the room
How to say it in the interview
talk track
- Draw the 3 arrows that change for one pair before coding. The recursive version is the cleanest first answer.
traps
- Losing the rest of the list by overwriting
second.nextbefore saving it.
what they ask next
Follow-ups
Reverse Nodes in k-Group (LC 25)?
Generalise: reverse the first k nodes, recurse on the rest, attach. Leave a final group shorter than k as it is.
before you submit
Edge cases to test
- Empty list → return null.
- One node → return it unchanged.
- Odd length: the last node has no partner and stays at the end.
practise next
Similar problems
- #206Reverse Linked ListEasyin Linked Lists
- #143Reorder ListMediumin Linked Lists