Free lesson · DSA Mastery - Interview Prep, End to End

Swap Nodes in Pairs

Medium6 min readdsalinked-list

Swap Nodes in Pairs

Swap Nodes in Pairs shifts from removal to rearrangement, and it comes with an explicit constraint that makes it a real pointer exercise: you must swap every two adjacent nodes by rewiring the nodes themselves, not by swapping their values. That forces you to juggle three pointers per swap - the predecessor, and the two nodes being exchanged - and it's a clean stepping-stone toward the in-place reversal techniques later in the module. We present the standard iterative dummy-head rewiring and a recursive formulation.

The discipline: each swap rewires three next pointers in a specific order, and a dummy head means even the first pair has a predecessor to anchor the rewire.

The Problem

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).

Example 1:

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

Example 2:

Input:  head = [1]
Output: [1]

Example 3:

Input:  head = []
Output: []

Constraints:

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

Approaches Overview

Both swap nodes (not values), respecting the constraint. The iterative version is O(1) space; the recursion is elegant but pays a stack cost. An odd trailing node is left in place.

Approach 1: Iterative Dummy-Head Rewiring - Optimal

The Idea

Anchor a prev pointer at a dummy before the head. For each pair (first, second) where first = prev.next and second = first.next, perform the swap with three rewires:

1. first.next = second.next - first now points past the pair.
2. second.next = first - second now precedes first.
3. prev.next = second - the predecessor now points to second (the new front of the pair).

Then advance prev to first (now the second node of the swapped pair) and repeat. Stop when fewer than two nodes remain.

Logic Flowchart

graph TD
    A["dummy -> head; prev = dummy"] --> B{"prev.next != null AND prev.next.next != null?"}
    B -->|No| C["Return dummy.next"]
    B -->|Yes| D["first = prev.next; second = first.next"]
    D --> E["first.next = second.next"]
    E --> F["second.next = first"]
    F --> G["prev.next = second"]
    G --> H["prev = first (advance past pair)"]
    H --> B

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This flowchart shows the iterative swap. From a dummy, for each pair we set first's next to past the pair, second's next to first, and the predecessor's next to second. Then we advance the predecessor to first, the new second node of the pair, and repeat while at least two nodes remain.

Code

public static ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;

    while (prev.next != null && prev.next.next != null) {
        ListNode first = prev.next;
        ListNode second = first.next;

        first.next = second.next;   // 1: first points past the pair
        second.next = first;        // 2: second precedes first
        prev.next = second;         // 3: predecessor points to second

        prev = first;               // advance past the swapped pair
    }
    return dummy.next;
}

// Usage:
// swapPairs([1,2,3,4]) -> [2,1,4,3]
// swapPairs([1])       -> [1]

This Java code uses a dummy before the head. For each adjacent pair it rewires three pointers: first points past the pair, second points to first, and the predecessor points to second. It then advances the predecessor to first and continues while at least two nodes remain.

Step-by-Step Walkthrough

A frame-by-frame trace on [1, 2, 3, 4]:

graph LR
    F0["prev=dummy<br/>first=1, second=2"]
    F1["rewire: 1.next=3<br/>2.next=1, dummy.next=2<br/>list 2,1,3,4"]
    F2["prev=1<br/>first=3, second=4"]
    F3["rewire: 3.next=null<br/>4.next=3, 1.next=4<br/>list 2,1,4,3"]
    F4["prev=3, next=null<br/>stop"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F4 fill:#b45309,stroke:#f59e0b,color:#f1f5f9

This walkthrough swaps pairs in one, two, three, four. The first pair becomes two, one with the dummy pointing to two, giving two, one, three, four. Advancing prev to node one, the second pair swaps to four, three, giving two, one, four, three. With no pair left, we stop.

Result: [2, 1, 4, 3].

Complexity

Time: O(n) - each node touched once. Space: O(1).

Approach 2: Recursive

The Idea

Swap the first two nodes, then recursively swap the rest and attach it. head and head.next are the pair: let second = head.next; set head.next = swapPairs(second.next) (the swapped remainder), then second.next = head, and return second as the new front. Base case: fewer than two nodes returns as-is.

Logic Flowchart

graph TD
    A["swapPairs(head)"] --> B{"head == null OR head.next == null?"}
    B -->|Yes| C["Return head"]
    B -->|No| D["second = head.next"]
    D --> E["head.next = swapPairs(second.next)"]
    E --> F["second.next = head"]
    F --> G["Return second"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the recursive swap. The second node becomes the new front; the head's next is set to the swapped remainder, then the second node points back to the head. The base case returns lists of fewer than two nodes unchanged.

Code

public static ListNode swapPairsRecursive(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode second = head.next;
    head.next = swapPairsRecursive(second.next);   // swapped remainder
    second.next = head;
    return second;                                  // new front of this pair
}

This Java code makes the second node the new front, sets the head's next to the recursively swapped remainder, and points the second node back to the head, returning the second node.

Complexity

Time: O(n). Space: O(n) stack.

Complexity Comparison

Both swap nodes (honoring the no-value-swap rule). The iterative version is the expected answer for O(1) space; recursion is concise but uses the call stack.

Variations & Follow-ups

Why not just swap the values?

The problem explicitly forbids it - you must rewire the nodes. Beyond the rule, value-swapping doesn't teach the pointer discipline that generalizes to k-group reversal (15.24), where nodes genuinely must move.

Why does the order of the three rewires matter?

Each rewire depends on a pointer the next one will overwrite. Saving first and second up front, then rewiring first.next, second.next, prev.next in that order, ensures no needed reference is lost.

How does this relate to Reverse Nodes in k-Group (15.24)?

Swapping pairs is reversing every group of size 2. The k-group problem generalizes it to arbitrary group sizes, using the same "rewire a fixed-size block, then advance the anchor" structure.

What about an odd number of nodes?

The loop condition prev.next != null && prev.next.next != null stops when fewer than two nodes remain, leaving the final lone node in place.

What about edge cases?

• Empty list: Returns null (Example 3).
• Single node: Returned unchanged (Example 2).
• Odd length: Last node stays put.
• Two nodes: One swap.

Common Interview Pitfalls

• Swapping values instead of nodes. Violates the constraint.
• Wrong rewire order, losing a reference. Save both pair nodes before rewiring.
• Forgetting to advance prev to first. After the swap, first is the pair's second node and the next pair's predecessor.
• Omitting the dummy. The first pair's swap changes the head; the dummy anchors it.

Why This Problem Matters

Swap Nodes in Pairs is the first true node-rearrangement problem - moving nodes by pointer surgery under an explicit no-value-swap rule. The three-rewire-per-pair discipline, anchored by a dummy, is exactly the muscle you'll need for in-place reversal, and recognizing pair-swapping as "reverse every group of two" sets up the k-group generalization directly.

The next topic, Copy List with Random Pointer, is a different kind of challenge entirely: deep-copying a list whose nodes carry an extra arbitrary pointer - solved either with a hash map from old nodes to new, or with a clever O(1)-space interleaving trick that weaves the copy into the original before splitting them apart.

Back to DSA Mastery - Interview Prep, End to End