Swap Nodes in Pairs
Swap Nodes in Pairs: given a linked list, swap every two adjacent nodes and return the new head. You must swap the nodes themselves, not just their values.
- The number of nodes in the list is in the range [0, 100].
- 0 <= Node.val <= 100
Intuition
Swap nodes in pairs exchanges every two adjacent nodes in a linked list, and the problem explicitly requires swapping the nodes themselves, not merely their values. Swapping values is a two-line solution that misses the point — the exercise is pointer manipulation.
For a pair A → B, the goal is B → A, with A then pointing at whatever the next pair becomes. Three pointers change: the node before the pair, and the two nodes within it.
The complication is that swapping the first pair changes the list's head, which would otherwise need a special case. A dummy node placed before the head removes it:
- With a dummy in front, every pair has a real predecessor, so the first pair is handled by the same code as every other.
Return dummy.next at the end rather than the original head, which is now the second node.
Walk with a prev pointer that always sits immediately before the pair being swapped. Three reassignments do the work: prev.next points at the second node, the first node points past the pair, and the second node points back at the first.
Order matters — save both nodes in locals before rewiring, or one assignment destroys a pointer the next one needs.
After the swap, the first node has become the pair's tail, so prev moves there. The loop continues while a full pair remains; a lone trailing node is left untouched, which is what the problem requires.
When a linked list problem asks you to rearrange nodes in fixed-size groups (pairs, triples, k-groups), the pattern is: use a prev pointer before the group, perform the pointer surgery, then advance prev past the rearranged group. A dummy node at the front unifies the first group with all others.
Approach
Before reading on: price up what the direct approach costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(n) time and O(1) space.
Use a dummy before the head
Create a dummy whose next is the head and return dummy.next at the end. The first swap changes the head, and the dummy makes that case identical to every other pair.
Keep prev before each pair
Maintain a pointer sitting immediately before the two nodes being swapped, starting at the dummy. It is the node whose next must be redirected to the pair's new front.
Save both nodes before rewiring
Assign first = prev.next and second = first.next into locals first. Rewiring without saving destroys a pointer the next assignment needs — the same ordering trap as Invert Binary Tree.
Perform the three reassignments
Set first.next = second.next, then second.next = first, then prev.next = second. The pair is now reversed and correctly joined to what precedes and follows it.
Advance prev past the pair
After the swap first is the pair's tail, so set prev = first. Continuing from second instead would re-swap the pair endlessly.
Leave a lone trailing node alone
Loop while both prev.next and prev.next.next exist. An odd final node stays in place, which is exactly what the problem specifies.
Cost of the traversal
Each node is visited once with constant pointer work, giving O(n) time and O(1) space. The recursive version is shorter but costs O(n) stack frames.
Solution & live demo
Common pitfalls
Swapping values instead of nodes
first.val, second.val = second.val, first.val
prev.next = second first.next = second.next second.next = first
The problem explicitly requires swapping nodes, not values. Value swapping is O(1) and tempting, but it violates the constraint and would fail if nodes carry additional data.
Forgetting to advance prev to first after the swap
prev = second
prev = first
After the swap, first is the second node of the pair — it is the last node before the next pair. Advancing prev to second (which is now the first node) skips over first and connects the next swap to the wrong predecessor.
Not using a dummy node, causing the head to be lost
prev = head first = head second = head.next
dummy = ListNode(0) dummy.next = head prev = dummy
Without a dummy, swapping the first pair changes the head of the list. You would need a separate variable to track the new head and special-case the first iteration. The dummy eliminates this.
Edge cases
prev.next is None, so the loop never runs. Return None.
prev.next.next is None, so no pair exists. The single node is returned unchanged.
The last node has no partner. The loop condition prev.next and prev.next.next stops before it, leaving the last node in place.