24. Swap Nodes in Pairs (Medium)

Problem

Given the head of a linked list, swap every two adjacent nodes and return the head. You must swap the nodes themselves, not their values.

Example

head = [1,2,3,4] → [2,1,4,3]
head = [] → []
head = [1] → [1]

LeetCode 24 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, collect values and rebuild

Collect all node values into a list, swap adjacent pairs, rebuild.

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

def swap_pairs(head):
    vals = []
    cur = head
    while cur:                                # L1: O(n) collect
        vals.append(cur.val)
        cur = cur.next
    for i in range(0, len(vals) - 1, 2):     # L2: swap adjacent pairs in-place
        vals[i], vals[i + 1] = vals[i + 1], vals[i]
    dummy = ListNode()
    tail = dummy
    for v in vals:                            # L3: O(n) rebuild
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

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

function swapPairs(head: ListNode | null): ListNode | null {
    const vals: number[] = [];
    let cur: ListNode | null = head;
    while (cur) { vals.push(cur.val); cur = cur.next; }  // L1: O(n) collect
    for (let i = 0; i < vals.length - 1; i += 2) {       // L2: swap adjacent pairs
        [vals[i], vals[i + 1]] = [vals[i + 1], vals[i]];
    }
    const dummy = new ListNode();
    let tail = dummy;
    for (const v of vals) {                               // L3: O(n) rebuild
        tail.next = new ListNode(v);
        tail = tail.next;
    }
    return dummy.next;
}

type ListNode struct {
    Val  int
    Next *ListNode
}

func swapPairs(head *ListNode) *ListNode {
    var vals []int
    cur := head
    for cur != nil { vals = append(vals, cur.Val); cur = cur.Next } // L1: O(n) collect
    for i := 0; i < len(vals)-1; i += 2 {                          // L2: swap adjacent pairs
        vals[i], vals[i+1] = vals[i+1], vals[i]
    }
    dummy := &ListNode{}
    tail := dummy
    for _, v := range vals { tail.Next = &ListNode{Val: v}; tail = tail.Next } // L3: O(n) rebuild
    return dummy.Next
}

final class Solution {
func swapPairs(_ head: ListNode?) -> ListNode? {
        var values = listValues(head)
        var index = 0
        while index + 1 < values.count {
            values.swapAt(index, index + 1)
            index += 2
        }
        return makeList(values)
    }
}

Where the time goes, line by line

Variables: n = number of nodes.

Line	Per-call cost	Times executed	Contribution
L1 (collect)	$O(1)$	n	$O(n)$
L2 (swap values)	$O(1)$	n/2	$O(n)$
L3 (rebuild)	$O(1)$	n	$O(n)$

Correct but allocates $O(n)$ extra space and new nodes. Violates the “swap nodes not values” spirit of the problem.

Complexity

Time: $O(n)$
Space: $O(n)$

Approach 2: Iterative dummy-head pointer rewiring (optimal)

Use a dummy head so the first pair has a predecessor to link into. Maintain prev pointing at the node before the current pair and cur pointing at the first node of the pair.

Before: prev -> cur -> cur.next -> next_pair -> ...
After:  prev -> cur.next -> cur -> next_pair -> ...

def swap_pairs(head):
    dummy = ListNode(0, head)               # L1: O(1) sentinel before head
    prev, cur = dummy, head
    while cur and cur.next:                 # L2: at least two nodes remain
        next_pair = cur.next.next           # L3: O(1) save remainder
        prev.next = cur.next               # L4: O(1) link prev to second node
        cur.next.next = cur               # L5: O(1) second node points back to first
        cur.next = next_pair              # L6: O(1) first node points to remainder
        prev = cur                         # L7: O(1) advance prev to first of swapped pair
        cur = next_pair                    # L8: O(1) advance cur to start of next pair
    return dummy.next

function swapPairs(head: ListNode | null): ListNode | null {
    const dummy = new ListNode(0, head);    // L1: O(1) sentinel before head
    let prev: ListNode = dummy;
    let cur: ListNode | null = head;
    while (cur && cur.next) {              // L2: at least two nodes remain
        const nextPair = cur.next.next;    // L3: O(1) save remainder
        prev.next = cur.next;             // L4: O(1) link prev to second node
        cur.next.next = cur;              // L5: O(1) second node points back to first
        cur.next = nextPair;             // L6: O(1) first node points to remainder
        prev = cur;                        // L7: O(1) advance prev
        cur = nextPair;                    // L8: O(1) advance cur
    }
    return dummy.next;
}

type ListNode struct {
    Val  int
    Next *ListNode
}

func swapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}          // L1: O(1) sentinel before head
    prev, cur := dummy, head
    for cur != nil && cur.Next != nil {     // L2: at least two nodes remain
        nextPair := cur.Next.Next           // L3: O(1) save remainder
        prev.Next = cur.Next               // L4: O(1) link prev to second node
        cur.Next.Next = cur               // L5: O(1) second node points back to first
        cur.Next = nextPair               // L6: O(1) first node points to remainder
        prev = cur                          // L7: O(1) advance prev
        cur = nextPair                      // L8: O(1) advance cur
    }
    return dummy.Next
}

final class Solution {
func swapPairs(_ head: ListNode?) -> ListNode? {
        let dummy = ListNode(0, head)
        var previous = dummy
        while let first = previous.next, let second = first.next {
            first.next = second.next
            second.next = first
            previous.next = second
            previous = first
        }
        return dummy.next
    }
}

Where the time goes, line by line

Variables: n = number of nodes.

Line	Per-call cost	Times executed	Contribution
L1 (dummy)	$O(1)$	1	$O(1)$
L2 (loop guard)	$O(1)$	n/2	$O(n)$
L3-L8 (rewire + advance)	$O(1)$ each	n/2	$O(n)$ ← dominates

Four pointer assignments per pair, n/2 pairs total. No allocation beyond the dummy head.

Complexity

Time: $O(n)$ , driven by L3-L8 (one pass, constant work per pair).
Space: $O(1)$ .

Pointer diagram for `[1, 2, 3, 4]`

Step 1 (cur=1, nextPair=3):
  dummy -> 1 -> 2 -> 3 -> 4
  After:  dummy -> 2 -> 1 -> 3 -> 4
  prev=1, cur=3

Step 2 (cur=3, nextPair=None):
  dummy -> 2 -> 1 -> 3 -> 4
  After:  dummy -> 2 -> 1 -> 4 -> 3
  prev=3, cur=None  (loop exits)

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Key takeaways

Always draw the before/after pointer diagram before coding; the four assignments (L4-L6) have one correct order.
The dummy head eliminates the “is this the first node?” special case.
prev = cur (not prev = cur.next) because after the swap, cur is the second of the two in the output order, and the next pair starts at nextPair.
This pattern generalizes directly to 25 (Reverse Nodes in k-Group), which does the same rewiring over a window of k nodes.

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

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

def from_list(vals):
    dummy = ListNode()
    cur = dummy
    for v in vals:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next

def swap_pairs(head):
    dummy = ListNode(0, head)
    prev, cur = dummy, head
    while cur and cur.next:
        next_pair = cur.next.next
        prev.next = cur.next
        cur.next.next = cur
        cur.next = next_pair
        prev = cur
        cur = next_pair
    return dummy.next

def _run_tests():
    assert to_list(swap_pairs(from_list([1, 2, 3, 4]))) == [2, 1, 4, 3]
    assert to_list(swap_pairs(from_list([]))) == []
    assert to_list(swap_pairs(from_list([1]))) == [1]
    assert to_list(swap_pairs(from_list([1, 2, 3]))) == [2, 1, 3]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

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

function toList(head: ListNode | null): number[] {
    const out: number[] = [];
    while (head) { out.push(head.val); head = head.next; }
    return out;
}

function fromList(vals: number[]): ListNode | null {
    const dummy = new ListNode();
    let cur = dummy;
    for (const v of vals) { cur.next = new ListNode(v); cur = cur.next; }
    return dummy.next;
}

function swapPairs(head: ListNode | null): ListNode | null {
    const dummy = new ListNode(0, head);
    let prev: ListNode = dummy, cur: ListNode | null = head;
    while (cur && cur.next) {
        const nextPair = cur.next.next;
        prev.next = cur.next; cur.next.next = cur; cur.next = nextPair;
        prev = cur; cur = nextPair;
    }
    return dummy.next;
}

console.assert(JSON.stringify(toList(swapPairs(fromList([1, 2, 3, 4])))) === JSON.stringify([2, 1, 4, 3]));
console.assert(JSON.stringify(toList(swapPairs(fromList([])))) === JSON.stringify([]));
console.assert(JSON.stringify(toList(swapPairs(fromList([1])))) === JSON.stringify([1]));
console.assert(JSON.stringify(toList(swapPairs(fromList([1, 2, 3])))) === JSON.stringify([2, 1, 3]));
console.log("all tests pass");

206. Reverse Linked List, the foundational pointer-reversal pattern
25. Reverse Nodes in k-Group, generalization of this problem to k nodes
19. Remove Nth Node from End of List, another dummy-head pattern

Linked List Pointer Rewiring, the link editing pattern for changing node order without losing the chain.
Recursion, the self similar call structure behind subtree, choice tree, and divide problems.

24. Swap Nodes in Pairs (Medium)

Problem

Try it yourself

Approach 1: Brute force, collect values and rebuild

Approach 2: Iterative dummy-head pointer rewiring (optimal)

Pointer diagram for [1, 2, 3, 4]

Key takeaways

Test cases

Related topics

Related concepts

Pointer diagram for `[1, 2, 3, 4]`