Swap Nodes in Pairs Solution

Problem

Given a linked list, swap every two adjacent nodes and return the new head. You must rearrange the nodes themselves — not their values — so this is a pure pointer manipulation problem.

→

→∅

[1,2,3,4]

Input: head = [1, 2, 3, 4]
Output: [2, 1, 4, 3]
Explanation: Node 2 swaps with Node 1, then Node 4 swaps with Node 3.

If the list has an odd number of nodes, the last unpaired node stays in place.

Input: head = [1, 2, 3]
Output: [2, 1, 3]

Intuition

Each swap only touches two nodes at a time: the second node in the pair becomes the new head of that pair, and the first node falls behind it. The tricky part is that the node before the pair must update its next pointer to the new pair head — a dummy head node makes this uniform across all pairs, including the very first one.

Approach 1 — Recursive

Think of the problem as: swap the first two nodes, then recursively solve the rest and attach the result to the first node's next.

Base case: if fewer than two nodes remain, return head unchanged.
Label the first node first and the second node second.
Recursively call on second.next to get the already-swapped tail.
Set second.next = first to reverse the current pair.
Set first.next to the processed tail.
Return second as the new head of this pair.

1class Solution:
2    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
3        if not head or not head.next:
4            return head
5
6        first = head
7        second = head.next
8
9        # recurse before relinking so the tail isn't lost when we rearrange pointers
10        remaining = self.swapPairs(second.next)
11
12        second.next = first
13        first.next = remaining
14
15        return second

Time: O(n) — each node is visited exactly once across all recursive calls.
Space: O(n) — the call stack grows to n/2 frames deep for n nodes.

Approach 2 — Iterative with Dummy Head

Use a sentinel node before the list so every pair always has a predecessor to update. Walk prev forward by two nodes each iteration.

Create a dummy node pointing to head; set prev = dummy.
While prev.next and prev.next.next both exist (at least two nodes remain):
Save first = prev.next, second = prev.next.next.
Set first.next = second.next — detach first from second, bridging over it.
Set second.next = first — second now leads the pair.
Set prev.next = second — attach the predecessor to the new pair head.
Advance prev = first — first is now the tail of the swapped pair.
Return dummy.next.

1class Solution:
2    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
3        dummy = ListNode(0, head)
4        prev = dummy
5
6        while prev.next and prev.next.next:
7            first = prev.next
8            second = prev.next.next
9
10            first.next = second.next   # first jumps over second to what comes after
11            second.next = first        # second points back at first, completing the swap
12            prev.next = second         # predecessor now leads into the swapped pair
13
14            prev = first               # first is the new tail; advance prev to it
15
16        return dummy.next

Time: O(n) — each node is visited exactly once.
Space: O(1) — only a constant number of extra pointers regardless of list length.

Complexity Summary

Approach	Time	Space	When to use
Recursive	O(n)	O(n)	When clarity matters more than stack depth; fine for short lists
Iterative (Dummy Head)	O(n)	O(1)	Production code or when stack overflow risk is a concern

Common Mistakes

Advancing prev to the wrong node — after swapping, first becomes the tail of the pair, so prev must advance to first, not second. Advancing to second revisits already-swapped nodes and produces wrong output.
Doing the pointer updates in the wrong order — you must save the rest of the list in first.next = second.next before setting second.next = first. Reversing these two lines loses the tail permanently.
Omitting the dummy head — without a dummy node, the list head changes after the first swap, requiring a special case. The dummy makes all iterations identical.
Incomplete base case in recursion — checking only if not head (missing not head.next) crashes on an odd-length list when one node remains with no pair.
Returning dummy instead of dummy.next — the sentinel node has value 0 and should never appear in the output; always return dummy.next.

Swap Nodes in Pairs — Solution