What is the brute force approach and complexity for Swap Nodes in Pairs?

Put the node pointers in a vector, swap neighbours there, then relink in the new order with time complexity O(N) and space complexity O(N).

What is the optimal approach and complexity for Swap Nodes in Pairs?

Walk pairs with prev, a and b, and relink the three arrows in the right order with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Swap Nodes in Pairs?

Look for key signals in the prompt: "swap every two adjacent nodes" indicates Each block of 2 nodes is reversed on its own, and the blocks keep their order → Groups of k with k = 2.; "singly linked list" indicates We can't look back, so keep a `prev` pointer to the node before the current block.; "swap nodes, not values" indicates Only relink the arrows. Nodes move because their `next` pointers change, not because their data is copied..

Swap Nodes in Pairs

Medium·LeetCode #24Basic Anchor

LeetCode

Jump:

30-Second Mental ModelLinked List — Reversal (Groups of k, k = 2)

Complexity:O(N)→O(N)

Key Insight

Walk the list one pair at a time, with prev just before the pair. For the pair a → b, change three arrows: prev → b, a → (b's old next), and b → a. Then move prev to a. A dummy node in front gives the first pair a prev too. Only pointers change, so the nodes and their values stay the same.

Core Validity Invariant

Everything before prev is already swapped, and the pair at prev->next is swapped only when both of its nodes exist.

Problem

You are given the head of a singly linked list. Swap every two neighbouring nodes, and return the head of the new list.

Swap the nodes, not the values. Each node keeps its own value, so only the next arrows may change. If the list has an odd number of nodes, the last node has no partner, so it stays where it is.

Input

head, the first node of a singly linked list. The list can be empty.

Output

The head of the list after the pairs are swapped.

Example 1

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

Output: [2, 1, 4, 3]

The pairs (1, 2) and (3, 4) swap places.

Example 2

Input: head = [1, 2, 3]

Output: [2, 1, 3]

The pair (1, 2) swaps. Node 3 has no partner, so it stays at the end.

Example 3

Input: head = [1]

Output: [1]

One node has no partner, so nothing changes.

Constraints

• The list has between 0 and 100 nodes.
• 0 ≤ Node.val ≤ 100
• Do not change any node's value. Only the `next` arrows may change.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I swap the first pair, which node becomes the new head?
2.
After I swap a pair, which node has to point to the first node of the next pair?
3.
The first pair has no node in front of it. How can I avoid writing a special case for it?
4.
Which next arrow do I overwrite first, and do I still need its old value afterwards?
5.
What should happen when only one node is left, or when the list is empty?

Brute force approach

Idea

An array makes the order easy to change. Store a pointer to each node in a vector, and swap each neighbouring pair of pointers in the vector. Then point every node at the entry after it in the vector. The nodes themselves are never copied, and no values change.

Thinking process

1
Swapping two neighbours is easy in an array: swap the two entries.
2
The list is only the order of the next arrows. So after the swap, the arrows must follow the new order.
3
So store the pointers in a vector, swap the entries, then rewrite each arrow.
4
Check on [1, 2, 3]: the vector is [1, 2, 3]. Swapping the pair (1, 2) gives [2, 1, 3]. Node 3 has no partner, so it stays last. Rewriting each arrow gives 2 → 1 → 3 → null.

Visual

The vec row holds pointers to the nodes, shown by their values. Swapping entries in vec reorders them, but the list arrows only change at the end. The list row shows the arrows as they are at each step; green = pushed or relinked.

Collect pointers, swap, relinkhead = [1, 2, 3, 4, 5]step 1/10

list

null

vec

▲last

Collect

pushed: node 0 (val 1)
vec size: 1

push pointer to node 0 (val 1)

Store a pointer to node 0 in vec. The values are not copied, only pointers.

Code & Implementation

brute.cpp

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        // Collect the node objects (not their values) in list order.
        vector<ListNode*> nodes;
        for (ListNode* cur = head; cur != nullptr; cur = cur->next) {
            nodes.push_back(cur);
        }
        // Swap each neighbouring pair of pointers in the array.
        // A leftover last node (odd count) has no partner, so it stays where it is.
        for (size_t i = 0; i + 1 < nodes.size(); i += 2) {
            swap(nodes[i], nodes[i + 1]);
        }
        // Relink every node to the one after it in the new array order.
        for (size_t i = 0; i < nodes.size(); i++) {
            nodes[i]->next = (i + 1 < nodes.size()) ? nodes[i + 1] : nullptr;
        }
        return nodes.empty() ? nullptr : nodes[0];
    }
};

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        // Collect the node objects (not their values) in list order.
        List<ListNode> nodes = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            nodes.add(cur);
        }
        // Swap each neighbouring pair of pointers in the array.
        // A leftover last node (odd count) has no partner, so it stays where it is.
        for (int i = 0; i + 1 < nodes.size(); i += 2) {
            ListNode temp = nodes.get(i);
            nodes.set(i, nodes.get(i + 1));
            nodes.set(i + 1, temp);
        }
        // Relink every node to the one after it in the new array order.
        for (int i = 0; i < nodes.size(); i++) {
            nodes.get(i).next = (i + 1 < nodes.size()) ? nodes.get(i + 1) : null;
        }
        return nodes.isEmpty() ? null : nodes.get(0);
    }
}

from typing import Optional, List, Dict, Tuple

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Collect the node objects (not their values) in list order.
        nodes: List[ListNode] = []
        cur = head
        while cur:
            nodes.append(cur)
            cur = cur.next
        # Swap each neighbouring pair of pointers in the array.
        # A leftover last node (odd count) has no partner, so it stays where it is.
        for i in range(0, len(nodes) - 1, 2):
            nodes[i], nodes[i + 1] = nodes[i + 1], nodes[i]
        # Relink every node to the one after it in the new array order.
        for i in range(len(nodes)):
            nodes[i].next = nodes[i + 1] if i + 1 < len(nodes) else None
        return nodes[0] if nodes else None

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

export function swapPairs(head: ListNode | null): ListNode | null {
    // Collect the node objects (not their values) in list order.
    const nodes: ListNode[] = [];
    for (let cur = head; cur !== null; cur = cur.next) {
        nodes.push(cur);
    }
    // Swap each neighbouring pair of pointers in the array.
    // A leftover last node (odd count) has no partner, so it stays where it is.
    for (let i = 0; i + 1 < nodes.length; i += 2) {
        const temp = nodes[i];
        nodes[i] = nodes[i + 1];
        nodes[i + 1] = temp;
    }
    // Relink every node to the one after it in the new array order.
    for (let i = 0; i < nodes.length; i++) {
        nodes[i].next = (i + 1 < nodes.length) ? nodes[i + 1] : null;
    }
    return nodes.length > 0 ? nodes[0] : null;
}

Complexity

Time O(N)Space O(N)

The vector holds n pointers, so this uses O(N) extra memory. The optimal version does the same job by changing only a few pointers.

Optimized approach

Idea

Start from brute force

The brute force stores every node in a vector so it can reorder the pointers. But we only ever swap one pair at a time, and the arrows already show the order. So we can change the arrows of each pair directly.

Find the repeated work

The vector copies n pointers only to reorder them, and then walks them again to relink. Each pair can be swapped as soon as we reach it. No second pass is needed.

Define the state — what variables do I need?

prev: The last node before the current pair. For the first pair it is the dummy node.
a / b: The first and second node of the current pair: a = prev->next and b = a->next.
dummy: A node in front of the list. dummy.next is the head, and it is the answer at the end, even if the head changed.

Define validity

Everything before prev is already swapped, and the pair at prev->next is swapped only when both of its nodes exist.

Define the transitions — when does each pointer move, and why is it safe?

A full pair is ahead (prev->next and prev->next->next exist)

a = prev->next; b = a->next; a->next = b->next; b->next = a; prev->next = b; prev = a;

Read b->next before it is overwritten. Then b can point back to a without losing the rest of the list. prev moves to a, which is now the end of the swapped pair.

Only one node is left, or none

Stop the loop. Return dummy.next.

A single node has no partner, so it stays where it is. The loop checks two nodes ahead, so it never reads a null pointer.

What does the current window add to the answer?

Each loop step fixes one pair. The pairs before prev never change again, so the result is built from left to right.

Code & Implementation

optimal.cpp

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        // A dummy node in front, so the first pair has a "prev" just like every other pair.
        ListNode dummy(0, head);
        ListNode* prev = &dummy;   // the last node before the pair we are about to swap

        // Each loop swaps one pair: prev -> a -> b  becomes  prev -> b -> a.
        // A single node left at the end has no partner, so the loop stops.
        while (prev->next != nullptr && prev->next->next != nullptr) {
            ListNode* a = prev->next;
            ListNode* b = a->next;

            // Three arrows change. Read b->next BEFORE b->next is overwritten,
            // or the rest of the list is lost.
            a->next = b->next;     // a skips over b, straight to the next pair
            b->next = a;           // b points back to a
            prev->next = b;        // the previous pair (or the dummy) now leads to b

            prev = a;              // a is now the second node of the pair, so it is the next "prev"
        }
        return dummy.next;
    }
};

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        // A dummy node in front, so the first pair has a "prev" just like every other pair.
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;   // the last node before the pair we are about to swap

        // Each loop swaps one pair: prev -> a -> b  becomes  prev -> b -> a.
        // A single node left at the end has no partner, so the loop stops.
        while (prev.next != null && prev.next.next != null) {
            ListNode a = prev.next;
            ListNode b = a.next;

            // Three arrows change. Read b.next BEFORE b.next is overwritten,
            // or the rest of the list is lost.
            a.next = b.next;     // a skips over b, straight to the next pair
            b.next = a;          // b points back to a
            prev.next = b;       // the previous pair (or the dummy) now leads to b

            prev = a;            // a is now the second node of the pair, so it is the next "prev"
        }
        return dummy.next;
    }
}

from typing import Optional, List, Dict, Tuple

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # A dummy node in front, so the first pair has a "prev" just like every other pair.
        dummy = ListNode(0, head)
        prev = dummy   # the last node before the pair we are about to swap

        # Each loop swaps one pair: prev -> a -> b  becomes  prev -> b -> a.
        # A single node left at the end has no partner, so the loop stops.
        while prev.next and prev.next.next:
            a = prev.next
            b = a.next

            # Three arrows change. Read b.next BEFORE b.next is overwritten,
            # or the rest of the list is lost.
            a.next = b.next     # a skips over b, straight to the next pair
            b.next = a          # b points back to a
            prev.next = b       # the previous pair (or the dummy) now leads to b

            prev = a            # a is now the second node of the pair, so it is the next "prev"
        return dummy.next

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

export function swapPairs(head: ListNode | null): ListNode | null {
    // A dummy node in front, so the first pair has a "prev" just like every other pair.
    const dummy = new ListNode(0, head);
    let prev: ListNode = dummy;   // the last node before the pair we are about to swap

    // Each loop swaps one pair: prev -> a -> b  becomes  prev -> b -> a.
    // A single node left at the end has no partner, so the loop stops.
    while (prev.next !== null && prev.next.next !== null) {
        const a: ListNode = prev.next;
        const b: ListNode = a.next!;

        // Three arrows change. Read b.next BEFORE b.next is overwritten,
        // or the rest of the list is lost.
        a.next = b.next;     // a skips over b, straight to the next pair
        b.next = a;          // b points back to a
        prev.next = b;       // the previous pair (or the dummy) now leads to b

        prev = a;            // a is now the second node of the pair, so it is the next "prev"
    }
    return dummy.next;
}

Complexity

Time O(N)Space O(1)

Each node is visited once, and only a few pointers are used. A recursive version makes the same three-arrow swap, then calls itself on the rest of the list. It is just as correct, but its recursion uses O(N/2) stack space, so the loop is the one to use.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Put the node pointers in a vector, swap neighbours there, then relink in the new order	O(N)	O(N)
Optimal	Walk pairs with prev, a and b, and relink the three arrows in the right order	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“swap every two adjacent nodes”Each block of 2 nodes is reversed on its own, and the blocks keep their order → Groups of k with k = 2.
“singly linked list”We can't look back, so keep a `prev` pointer to the node before the current block.
“swap nodes, not values”Only relink the arrows. Nodes move because their `next` pointers change, not because their data is copied.

Blocks of k = 2+reverse each block in place+prev → block head, block tail → next block→Linked List — Reversal (Groups of k, k = 2)

A pair is a block of size 2. Reversing a block of 2 means swapping its two nodes, which is exactly the three-arrow change. The node before the pair is the prev pointer, and it must be joined to the new head of the block, which is b. This is the easiest group because the block size is fixed at 2, so there is no counting ahead. The only check is that two nodes exist. Groups of k must first count k nodes, and decide what to do with a short last block.

Don't make this mistake

Reversing the whole list (pattern confusion)

✗ return reverse(head); // 1 → 2 → 3 → 4 becomes 4 → 3 → 2 → 1

✓ Swap each pair only: 1 2 3 4 becomes 2 1 4 3.

This is the pattern-confusion trap: full reversal flips every arrow in the list, but this question only swaps each pair. On the dry run [1, 2, 3, 4, 5], reversing everything gives 5 → 4 → 3 → 2 → 1. The answer is 2 → 1 → 4 → 3 → 5, where 3 pairs with 4, not with 1.

Swapping the values instead of the nodes

✗ swap(a->val, b->val); // the numbers move, the nodes stay where they are

✓ prev->next = b; a->next = b->next; b->next = a;

The printed list looks right, but the node objects did not move. The statement only lets the next arrows change, and the test checks the node identities, so this fails. Relink the nodes instead.

Losing the rest of the list in the middle of the three arrows

✗ prev->next = b; b->next = a; a->next = b->next; // b->next is already a, so a->next = a

✓ a->next = b->next; // read b->next first b->next = a; prev->next = b;

Order matters. After b->next = a, the node b no longer knows the next pair. Now b->next is a, so a->next = b->next sets a->next = a. The node points at itself, so the rest of the list is lost and any walk loops forever. On [1, 2, 3, 4, 5] the walk from the dummy becomes 2 → 1 → 1 → 1 … forever. Read b->next before you overwrite it.

Not checking for a full pair (the odd node)

✗ while (prev->next != nullptr) { // a = prev->next; b = a->next; ... // b is null when the count is odd, so b->next crashes

✓ while (prev->next != nullptr && prev->next->next != nullptr) { ... }

With an odd number of nodes, the last node has no partner. If the loop only checks prev->next, then b is null and b->next crashes. Check that both nodes of the pair exist before touching them.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Linked List — Reversal translate into production architectures and low-level memory mechanics.

LLD Architecture