Swap Nodes in Pairs

The Problem

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

Example 1:

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

Output: [2,1,4,3]

Explanation:

Example 2:

Input: head = []

Output: []

Example 3:

Input: head = [1]

Output: [1]

Example 4:

Input: head = [1,2,3]

Output: [2,1,3]

Constraints:

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

Step 01

The Brute Force Temptation

The most obvious approach: just swap the values of each pair of nodes. Walk through two at a time and exchange their data.

Value-Swapping Approach

// Tempting but VIOLATES the constraint!
while (curr != null && curr.next != null) {
    int temp = curr.val;
    curr.val = curr.next.val;    // swap values
    curr.next.val = temp;
    curr = curr.next.next;
}

// Tempting but VIOLATES the constraint!
for curr != nil && curr.Next != nil {
    curr.Val, curr.Next.Val = curr.Next.Val, curr.Val  // swap values
    curr = curr.Next.Next
}

# Tempting but VIOLATES the constraint!
while curr and curr.next:
    curr.val, curr.next.val = curr.next.val, curr.val  # swap values
    curr = curr.next.next

// Tempting but VIOLATES the constraint!
while let Some(ref mut node) = curr {
    if let Some(ref mut next) = node.next {
        std::mem::swap(&mut node.val, &mut next.val); // swap values
        curr = next.next.take();
    } else { break; }
}

// Tempting but VIOLATES the constraint!
while (curr !== null && curr.next !== null) {
    const temp = curr.val;
    curr.val = curr.next.val;    // swap values
    curr.next.val = temp;
    curr = curr.next.next;
}

This looks clean and runs in O(n), but the problem explicitly says: "You must solve it without modifying the values in the nodes."

⚠️

Why this constraint? In real systems, nodes carry complex payloads (not just integers). Swapping pointers is O(1) regardless of data size. Swapping values could be expensive or impossible if the data is immutable. The constraint teaches you proper pointer manipulation — a fundamental linked list skill.

We need to actually rewire the pointers so the nodes physically change position in the list. This is where the dummy node technique shines.

Step 02

The Core Insight — Dummy Node + Pointer Rewiring

We create a dummy node pointing to the head, then use a prev pointer to rewire each pair. For every pair of adjacent nodes (first and second), we perform exactly three pointer changes:

The Three Pointer Rewires

1. first.next = second.next

First node skips over second, pointing to whatever comes after the pair.

2. second.next = first

Second node points back to first, completing the swap within the pair.

3. prev.next = second

The preceding node now points to second (which is the new front of the pair).

Let's see the before and after of rewiring a single pair:

Before Rewiring

P

1

first

→

2

second

→

3

→

4

→ null

After Rewiring

P

2

second

→

1

first

→

3

→

4

→ null

After the swap, prev advances to first (now at position 2), and we repeat for the next pair.

💡

Why a dummy node? The head of the list changes after the first swap (node 2 becomes the new head). A dummy node lets us treat the head swap exactly like any other swap — no special cases needed. We just return dummy.next at the end.

Step 03

Algorithm Walkthrough

Let's trace through the complete algorithm for the input [1, 2, 3, 4] step by step.

Initial State

Create a dummy node pointing to the head. Set prev = dummy.

D

dummy

1

→

2

→

3

→

4

→ null

Iteration 1 — Identify Pair (1, 2)

first = prev.next = 1, second = prev.next.next = 2

D

1

first

→

2

second

→

3

→

4

→ null

Apply the three rewires:

        first.next = second.next   // 1 → 3

        second.next = first        // 2 → 1

        prev.next = second         // D → 2

After Iteration 1

Pair (1,2) is swapped. Advance: prev = first (prev moves to node 1).

D

dummy

→

2

new head

→

1

3

→

4

→ null

Iteration 2 — Identify Pair (3, 4)

first = prev.next = 3, second = prev.next.next = 4

D

→

2

→

1

3

first

→

4

second

→ null

Apply the three rewires:

        first.next = second.next   // 3 → null

        second.next = first        // 4 → 3

        prev.next = second         // 1 → 4

Final State

Both pairs are swapped. prev.next (node 3) has no next pair, so the loop exits. Return dummy.next.

D

dummy

→

2

→

1

→

4

→

3

→ null

Result: [2, 1, 4, 3]

Step 04

Edge Cases

The algorithm handles all edge cases naturally through its loop condition: prev.next != null && prev.next.next != null.

Empty List

null

Loop never executes.
Returns null.

Single Node

1

→ null

prev.next.next is null.
Loop never executes. Returns [1].

Odd Count

2

→

1

→

3

[1,2,3] becomes [2,1,3].
Last node stays in place.

⚡

No special-case code needed. The while-loop condition prev.next != null && prev.next.next != null naturally stops when there are fewer than two nodes remaining. A single trailing node is simply left untouched.

Step 05

Full Annotated Code

class Solution {
    public ListNode swapPairs(ListNode head) {

        // Dummy node simplifies head-swap edge case
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;

        // Keep going while there are at least 2 nodes ahead
        while (prev.next != null && prev.next.next != null) {

            // Identify the pair
            ListNode first  = prev.next;        // 1st node of pair
            ListNode second = prev.next.next;   // 2nd node of pair

            // === Three pointer rewires ===
            first.next  = second.next;   // first skips over second
            second.next = first;          // second points back to first
            prev.next   = second;         // prev connects to second (new front)

            // Advance prev to first (now 2nd in the pair)
            prev = first;
        }

        return dummy.next;  // dummy.next is the new head
    }
}

func swapPairs(head *ListNode) *ListNode {

    // Dummy node simplifies head-swap edge case
    dummy := &ListNode{Next: head}
    prev := dummy

    // Keep going while there are at least 2 nodes ahead
    for prev.Next != nil && prev.Next.Next != nil {

        // Identify the pair
        first := prev.Next        // 1st node of pair
        second := prev.Next.Next  // 2nd node of pair

        // === Three pointer rewires ===
        first.Next = second.Next  // first skips over second
        second.Next = first        // second points back to first
        prev.Next = second         // prev connects to second (new front)

        // Advance prev to first (now 2nd in the pair)
        prev = first
    }

    return dummy.Next  // dummy.Next is the new head
}

class Solution:
    def swap_pairs(self, head: Optional[ListNode]) -> Optional[ListNode]:

        # Dummy node simplifies head-swap edge case
        dummy = ListNode(0, head)
        prev = dummy

        # Keep going while there are at least 2 nodes ahead
        while prev.next and prev.next.next:

            # Identify the pair
            first  = prev.next          # 1st node of pair
            second = prev.next.next     # 2nd node of pair

            # === Three pointer rewires ===
            first.next  = second.next   # first skips over second
            second.next = first          # second points back to first
            prev.next   = second         # prev connects to second (new front)

            # Advance prev to first (now 2nd in the pair)
            prev = first

        return dummy.next  # dummy.next is the new head

impl Solution {
    pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        // Recursive approach: swap first two, recurse on the rest
        if let Some(mut first) = head {
            if let Some(mut second) = first.next.take() {
                // first.next = recursive result starting from second.next
                first.next = Self::swap_pairs(second.next.take());
                // second.next = first (complete the swap)
                second.next = Some(first);
                return Some(second);
            }
            return Some(first);
        }
        None
    }
}

function swapPairs(head: ListNode | null): ListNode | null {

    // Dummy node simplifies head-swap edge case
    const dummy = new ListNode(0, head);
    let prev: ListNode = dummy;

    // Keep going while there are at least 2 nodes ahead
    while (prev.next !== null && prev.next.next !== null) {

        // Identify the pair
        const first  = prev.next;        // 1st node of pair
        const second = prev.next.next;   // 2nd node of pair

        // === Three pointer rewires ===
        first.next  = second.next;   // first skips over second
        second.next = first;          // second points back to first
        prev.next   = second;         // prev connects to second (new front)

        // Advance prev to first (now 2nd in the pair)
        prev = first;
    }

    return dummy.next;  // dummy.next is the new head
}

🔎

Order matters! The three assignments must happen in this exact sequence. If you set prev.next = second first, you lose the reference to first. If you set second.next = first before saving second.next, you lose the rest of the list. Think of it as: save the tail, link backward, then connect from the front.

Step 06

Interactive Demo

Enter list values and step through the pair-swapping algorithm. Watch the pointer rewiring happen node by node.

⚙ Swap Nodes Visualizer

List values

Step 07

Complexity Analysis

Time

O(n)

Space

O(n)

We traverse the list once, processing two nodes per iteration. Each swap performs exactly three pointer assignments -- constant work per pair. With n/2 pairs, the total work is O(n). The only extra memory is the dummy node and a few pointer variables, giving O(1) auxiliary space.

Approach Breakdown

RECURSIVE

O(n) time

O(n) space

Each recursive call swaps one pair and recurses on the rest, visiting all n nodes once for O(n) time. The call stack holds n/2 frames (one per pair), giving O(n) space from recursion depth alone.

ITERATIVE

O(n) time

O(1) space

A single while-loop processes two nodes per iteration with exactly three pointer rewires per pair. With n/2 pairs the loop runs n/2 times for O(n) total. Only a dummy node and a few pointer variables are allocated -- true O(1) auxiliary space.

🎯

Pointer manipulation is O(1) per pair; we visit n/2 pairs, giving O(n) total. A recursive solution is elegant but uses O(n/2) = O(n) stack space. The iterative approach here achieves true O(1) space, which is optimal for linked list manipulation problems.

Swap Nodes
in Pairs

Problem Statement

Roadmap

The Brute Force Temptation

Value-Swapping Approach

The Core Insight — Dummy Node + Pointer Rewiring

The Three Pointer Rewires

Before Rewiring

After Rewiring

Algorithm Walkthrough

Edge Cases

Full Annotated Code

Interactive Demo

⚙ Swap Nodes Visualizer

Complexity Analysis

Approach Breakdown

Common Mistakes

Losing head/tail while rewiring

Swap Nodesin Pairs

Problem Statement

Roadmap

The Brute Force Temptation

Value-Swapping Approach

The Core Insight — Dummy Node + Pointer Rewiring

The Three Pointer Rewires

Before Rewiring

After Rewiring

Algorithm Walkthrough

Edge Cases

Full Annotated Code

Interactive Demo

⚙ Swap Nodes Visualizer

Complexity Analysis

Approach Breakdown

Common Mistakes

Losing head/tail while rewiring

Swap Nodes
in Pairs