[/dsa/leetcode]

24 - Swap Nodes in Pairs

Saturday, 19 September 2026

<medium> [problem]

Three link writes per pair, anchored on a dummy so the node before every pair always exists and the changing head needs no special case.

{linked list}{recursion}

Problem

Given a linked list, swap every two adjacent nodes and return its head. The values may not be modified — only the nodes themselves may be changed.

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

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

Input: head = []
Output: []

Constraints:

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

Approach

Swapping a pair is three writes. Name the pair f and s, and call the node before them prev:

prev -> f -> s -> t

f->next = s->next     f -> t        (s->next read while still original)
s->next = f           s -> f -> t
prev->next = s        prev -> s -> f -> t

Then the loop just walks prev forward. After a swap, f is the second node of the pair, so f is exactly the node before the next pair:

[1,2,3,4]

prev = dummy   f = 1  s = 2   1 -> 3, 2 -> 1, dummy -> 2      prev = 1
prev = 1       f = 3  s = 4   3 -> null, 4 -> 3, 1 -> 4       prev = 3
prev = 3       prev->next = null, stop

dummy -> 2 -> 1 -> 4 -> 3
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(0, head);
        ListNode* prev = &dummy;
        while (prev->next && prev->next->next) {
            ListNode* f = prev->next;
            ListNode* s = f->next;
            f->next = s->next;
            s->next = f;
            prev->next = s;
            prev = f;
        }
        return dummy.next;
    }
};

The recursive version

ListNode* swapPairs(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* s = head->next;
    head->next = swapPairs(s->next);
    s->next = head;
    return s;
}
  • time: O(n) - each node is visited once
  • space: O(1) - three pointers and a stack-allocated dummy
quantinium © 2026