Swap Nodes in Pairs
Understanding the Problem
We need to take every consecutive pair of nodes in a linked list and swap their positions. So node 1 and node 2 swap, node 3 and node 4 swap, and so on. If the list has an odd number of nodes, the last node stays where it is.
The constraint that matters is that we cannot swap values. We have to rewire the node pointers. Swapping two adjacent nodes in a singly linked list requires updating three pointers: the two nodes in the pair, plus the node that points into the pair. Miss the third one and the chain breaks.
For each pair, then, we need to track three nodes: the node before the pair (so we can rewire its next), the first node in the pair, and the second node in the pair. A dummy node before the head simplifies the first swap, since the head itself has no predecessor.
Key Constraints:
0 <= n <= 100→ The list can be empty or have a single node, so both approaches must handle a list with fewer than two nodes without touching any pointers.0 <= Node.val <= 100→ The values do not affect the algorithm, since we rearrange nodes rather than read their values.Cannot modify node values→ This rules out the shortcut of swapping.valbetween adjacent nodes. We have to rearrange the nodes themselves, which is what makes the pointer work necessary.
Approach 1: Recursive
Intuition
Swapping the whole list reduces to swapping one pair plus swapping everything after it. If we have at least two nodes, we swap the first two, then recursively swap the rest of the list starting at the third node. The base case is fewer than two nodes remaining, where there is nothing to swap.
The connection between the two halves is the link out of the pair. After swapping nodes 1 and 2, node 1 ends up in the second position, so its next should point to the head returned by recursively swapping the rest of the list. Because each recursive call returns the new head of its swapped sublist, attaching that result to node 1 stitches the pairs together correctly.
Algorithm
- If the list is empty or has only one node, return the head as-is (base case).
- Let
first= head andsecond= head.next. - Recursively swap the sublist starting from
second.next(the third node onward). - Set
first.nextto the result of the recursive call. - Set
second.nexttofirst. - Return
secondas the new head of this swapped pair.
Example Walkthrough
Code
- Time Complexity: O(n). Each recursive call processes exactly two nodes, so we make n/2 calls. Each call does O(1) work. Total: O(n).
- Space Complexity: O(n). The recursion stack goes n/2 levels deep (one level per pair). In the worst case, this is O(n) space.
The recursion is correct, but it carries O(n) stack space. The next approach does the same rewiring with a single pointer walking the list, which brings the space down to O(1).
Approach 2: Iterative with Dummy Node
Intuition
The iterative approach processes pairs from left to right using a pointer that tracks the node immediately before each pair. A dummy node pointing to the head serves as the "previous" node for the first pair, so the head no longer needs special handling: when the first pair swaps, dummy.next updates to the new head along with every other rewiring.
For each pair, we do three pointer rewirings:
- The previous node's
nextshould point to the second node (which becomes the new first in the pair). - The first node's
nextshould point to whatever comes after the pair. - The second node's
nextshould point to the first node.
After the swap, the first node sits in the second position of the pair, so it becomes the "previous" node for the next pair. Advancing prev to the second node instead would skip the swap of the following pair, so the pointer has to land on the first node.
Before any rewiring, first and second both hold live references, so we can read second.next (the node after the pair) at any point. The order used here, prev.next = second then first.next = second.next then second.next = first, keeps that read valid: first.next = second.next runs while second.next still points past the pair, and only the final line overwrites it. Reordering so that second.next = first runs before we read second.next would lose the reference to the rest of the list.
Algorithm
- Create a dummy node with
dummy.next = head. - Initialize
prev = dummy. - While
prev.nextandprev.next.nextare not null (there's a complete pair): - Let
first = prev.nextandsecond = prev.next.next. - Rewire:
prev.next = second,first.next = second.next,second.next = first. - Advance:
prev = first(first is now in the second position of the swapped pair). - Return
dummy.next.
Example Walkthrough
Code
- Time Complexity: O(n). We traverse the list once, processing two nodes per iteration. The loop runs n/2 times with O(1) work each. Total: O(n).
- Space Complexity: O(1). We only use a constant number of pointers (
dummy,prev,first,second). No recursion stack, no extra data structures.