Swap Nodes in Pairs — In-Place Pointer Rewiring Without Swapping Values

Problem Statement#

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed).

Constraints:

• The number of nodes in the list is in the range [0, 100]
• 0 <= Node.val <= 100

Example 1:

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

Example 2:

Input:  head = []
Output: []

Example 3:

Input:  head = [1]
Output: [1]
Explanation: Single node — nothing to swap.

Why This Problem Matters#

Swap Nodes in Pairs (LeetCode 24) is the canonical test of multi-step pointer manipulation precision. Microsoft and Bloomberg use it in interviews because it requires you to correctly wire four pointer assignments in the right order without losing any node references. The constraint that you cannot swap values — only the nodes — forces you to engage with pointer mechanics rather than the easier value-swap shortcut.

The problem is a direct precursor to Reverse Nodes in K-Group (LeetCode 25), where you reverse groups of k nodes instead of pairs. If you can't swap pairs cleanly, you can't generalize to k-group reversal. Interviewers use this as a stepping stone to gauge how far up the difficulty ladder you can go.

The recursive version of this problem is also frequently asked as a demonstration of how to express iterative pointer operations as elegant recursive decomposition. Both versions should be in your toolkit.

In systems engineering, swapping adjacent elements in a linked list appears in certain sorting algorithms (bubble sort on linked lists), scheduling algorithms (priority adjustment), and certain graph traversal applications where adjacency relationships need reordering.

The Core Insight#

For swapping pairs, you need four pointer operations per pair. Given prev -> a -> b -> rest:

1. prev.next = b — wire prev to the second node
2. a.next = b.next — wire first node to what comes after second (= rest)
3. b.next = a — wire second node to first (completing the swap)
4. Advance prev = a — a is now the tail of the swapped pair

The dummy node serves as the initial prev, handling the first pair's swap without special casing.

The order of these operations is critical. If you do b.next = a before a.next = b.next, you lose the reference to rest.

Visual Dry Run#

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

Setup: dummy -> 1 -> 2 -> 3 -> 4

Iteration 1: prev = dummy, a = 1, b = 2

Iteration 2: prev = 1, a = prev.next = 3, b = prev.next.next = 4

Loop check: prev.next = None, prev.next.next doesn't exist. Loop ends.

Output: dummy.next = 2 -> 1 -> 4 -> 3

Solution (Optimal)#

Python — Iterative#

def swapPairs(head):
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy
 
    while prev.next and prev.next.next:
        a = prev.next         # first node of the pair
        b = prev.next.next    # second node of the pair
 
        # Four-step pointer rewire
        prev.next = b         # 1. link prev to second
        a.next = b.next       # 2. link first to after second (save b.next first!)
        b.next = a            # 3. link second to first
        prev = a              # 4. advance prev to tail of swapped pair
 
    return dummy.next

Important: a.next = b.next must happen before b.next = a. If you do b.next = a first, b.next is overwritten and you lose the reference to rest.

Time complexity: O(n) — each pair processed once.

Space complexity: O(1) — iterative, pointer variables only.

Python — Recursive#

def swapPairs(head):
    # Base case: 0 or 1 nodes — nothing to swap
    if not head or not head.next:
        return head
 
    a = head
    b = head.next
 
    # a's next becomes the result of swapping the remaining pairs
    a.next = swapPairs(b.next)
    # b points to a (swap the current pair)
    b.next = a
    # b is now the new head of this pair
    return b

JavaScript — Iterative#

var swapPairs = function(head) {
    const dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
 
    while (prev.next !== null && prev.next.next !== null) {
        const a = prev.next;
        const b = prev.next.next;
 
        prev.next = b;
        a.next = b.next;
        b.next = a;
        prev = a;
    }
 
    return dummy.next;
};

Complexity:

Common Mistakes#

1. Doing b.next = a before a.next = b.next. Once you write b.next = a, the reference to the rest of the list (b.next before the write) is gone. Always save or use b.next first: a.next = b.next, then b.next = a.

2. Not using a dummy node. Without dummy, the first pair swap changes the head. You need to handle the return value manually. With dummy, dummy.next always points to the correct new head.

3. Wrong loop condition. while prev.next and prev.next.next — you need both conditions. If only one node remains (odd-length list), you skip the last node (correct — it has no pair). Checking only prev.next would try to access prev.next.next on a single remaining node.

4. Advancing prev to b instead of a. After the swap, a is the tail of the pair (it comes second). The next pair starts at a.next. So prev = a is correct. Setting prev = b would skip the tail of the current pair.

5. Confusing the recursive base case. The base case is if not head or not head.next: return head. If you only check if not head, a single-node list falls through into the recursive step, causing an error when accessing head.next.next.

Interview Tips#

1. Draw it before coding: Draw prev -> a -> b -> rest and label all four pointer changes. This prevents the ordering mistake.

2. Use variable names a and b: Much clearer than first/second or node1/node2. Interviewers follow along easily.

3. State the order explicitly: "I assign a.next = b.next before b.next = a to avoid losing the reference to the rest."

4. Offer both versions: After the iterative solution, volunteer: "The recursive version is more elegant — want me to show it?" This differentiates you.

5. Bridge to Reverse in K-Group: "This is a special case of LC 25 Reverse Nodes in K-Group with k=2. The same pointer mechanics apply, just with a loop inside each group."

Follow-up Questions#

Q: How does this generalize to Reverse Nodes in K-Group (LC 25)? Instead of swapping 2 nodes, you reverse k nodes. The structure is: find group of k, reverse it using the 3-pointer pattern, reconnect to the rest. For k=2, that's exactly this problem.

Q: Can you do it by swapping values instead of nodes? The problem explicitly prohibits this. But yes — a.val, b.val = b.val, a.val then advance by 2 would work trivially in O(n). The constraint forces you to work with pointers.

Q: What if the list has an odd number of nodes? The last unpaired node is left as-is. The loop condition prev.next and prev.next.next ensures we stop when only one node remains.

Q: Is the recursive version tail-recursive? No — b.next = a happens after the recursive call returns. It's not tail-recursive. Python doesn't optimize tail recursion anyway, so for large lists the iterative version is safer.

Q: What's the space complexity of the recursive version? O(n/2) = O(n) — one recursive call per pair, so n/2 stack frames.

Key Takeaways#

• Four pointer operations per pair: prev.next = b, a.next = b.next, b.next = a, prev = a. Order matters.
• a.next = b.next must come before b.next = a — save the reference to rest before overwriting.
• The dummy head handles the first pair without special cases and gives a stable return anchor.
• After swapping, a is the tail of the pair — advance prev = a.
• The recursive version is elegant: swap the first pair, recurse on the rest, wire together.
• This is the k=2 special case of Reverse Nodes in K-Group — mastering this makes LC 25 approachable.