Swap Nodes in Pairs (LeetCode 24)

The problem

You get the head of a linked list. Swap every two adjacent nodes and return the new head. You must move the nodes themselves; swapping the val fields is not allowed. If the list has an odd length, the last node stays where it is.

Input:  1 -> 2 -> 3 -> 4
Output: 2 -> 1 -> 4 -> 3

Pairs (1, 2) and (3, 4) each swap places.

How to think about it

Start with brute force. Copy the values into an array, swap neighbours there, and write them back. It works in O(n) time but uses O(n) space and breaks the “don’t modify values” rule. An interviewer wants pointer surgery.

The key insight: a swap is a reversal of a group of size 2. For a pair a -> b sitting between a node prev and the rest of the list, the goal is prev -> b -> a -> rest. That takes exactly three pointer writes, done in the right order so nothing is lost:

1. a.next = b.next (a now points to the rest),
2. b.next = a (b points back to a),
3. prev.next = b (the earlier part now enters at b).

Use a dummy head. The very first pair has no real prev, and its swap changes the head of the list. A dummy node in front gives every pair, including the first, a prev. After a swap, a is the second node of the pair, so it becomes the prev for the next pair.

Which pattern is this? Linked-list in-place reversal, with a fixed group size of 2. The tell is “rearrange nodes in groups without changing values”. The general version is Reverse Nodes in k-Group.

Approach

1. Create d = ListNode(0, head) and set prev = d.
2. While there are at least two nodes after prev:
   • name them a = prev.next and b = a.next,
   • rewire: a.next = b.next, b.next = a, prev.next = b,
   • move prev to a.
3. Return d.next.

Solution

class ListNode:                                   # LeetCode's node type
    def __init__(self, val=0, next=None):
        self.val = val; self.next = next

def swap_pairs(head):
    d = ListNode(0, head); prev = d               # dummy: the first pair also has a prev
    while prev.next and prev.next.next:           # need a full pair
        a = prev.next; b = a.next
        # prev -> a -> b -> rest   becomes   prev -> b -> a -> rest
        a.next = b.next; b.next = a; prev.next = b; prev = a
    return d.next
# swap_pairs([1,2,3,4]) -> [2,1,4,3]

Dry run

On 1 -> 2 -> 3 -> 4:

Return d.next, which is node 2.

Complexity

• Time: O(n). Each pair is handled once with a constant number of pointer writes.
• Space: O(1). One dummy node and a few pointers. The recursive solution uses O(n) stack.

Edge cases and pitfalls

• Empty list or one node: the loop condition fails at once and the input is returned unchanged.
• Odd length: the last node has no partner, so the loop stops and it stays at the end. swap_pairs([1,2,3]) gives [2,1,3].
• Wrong write order. Doing b.next = a before a.next = b.next overwrites the only link to the rest of the list, and a.next = b.next then points a at itself.
• Advancing prev to b. After the swap b is in front; the node before the next pair is a.
• Swapping values. Easy, but explicitly against the rules.

Related problems

• Reverse Nodes in k-Group (LeetCode 25): the general case; with k = 2 it gives the same answer.
• Reverse Linked List (LeetCode 206): the base pointer-flip this builds on.
• Odd Even Linked List (LeetCode 328): another rearrangement by node position, not value.