LeetCode 24: Swap Nodes in Pairs

A detailed explanation of swapping every two adjacent nodes in a linked list using pointer manipulation.

leetcodelinked-listrecursion

Problem Restatement

We are given the head of a linked list.

We need to swap every two adjacent nodes and return the modified list head.

We are not allowed to modify node values. We must change the actual node links.

For example:

1 -> 2 -> 3 -> 4

becomes:

2 -> 1 -> 4 -> 3

The problem statement explicitly requires changing nodes themselves instead of only swapping values. The constraints say the number of nodes is in the range [0, 100] and node values are between 0 and 100.

Input and Output

Item Meaning
Input Head of a singly linked list
Output Head after swapping adjacent node pairs
Swap rule Every two adjacent nodes
Node values Must not be modified
Empty list Allowed

Example function shape:

def swapPairs(head: ListNode) -> ListNode:
    ...

Examples

Example 1:

head = [1,2,3,4]

Swap pairs:

(1,2) -> (2,1)
(3,4) -> (4,3)

Output:

[2,1,4,3]

Example 2:

head = []

Output:

[]

Example 3:

head = [1]

A single node has no partner to swap with.

Output:

[1]

First Thought: Swap Values

One possible idea is:

node1.val, node2.val = node2.val, node1.val

This would produce the correct visible ordering.

But the problem specifically forbids modifying values.

We must change the node connections themselves.

Key Insight

To swap two adjacent nodes:

a -> b

we need:

b -> a

The tricky part is preserving the rest of the list.

Suppose we have:

prev -> a -> b -> next_pair

After swapping:

prev -> b -> a -> next_pair

We only need to carefully update pointers in the correct order.

A dummy node makes the first swap easier because the head itself may change.

Pointer Structure

Before swapping:

dummy -> 1 -> 2 -> 3 -> 4
          a    b

After swapping a and b:

dummy -> 2 -> 1 -> 3 -> 4

The next iteration starts from node 1.

Visual Walkthrough

Use:

1 -> 2 -> 3 -> 4

Create:

dummy -> 1 -> 2 -> 3 -> 4

Set:

prev = dummy

First pair:

a = 1
b = 2

Store:

next_pair = 3

Now update pointers.

Step 1:

prev.next = b

Result:

dummy -> 2
1 -> 2 -> 3 -> 4

Step 2:

b.next = a

Result:

dummy -> 2 -> 1

Step 3:

a.next = next_pair

Result:

dummy -> 2 -> 1 -> 3 -> 4

Move:

prev = a

Now process:

3 -> 4

Final result:

2 -> 1 -> 4 -> 3

Algorithm

  1. Create a dummy node pointing to head.
  2. Set prev = dummy.
  3. While there are at least two nodes remaining:
    • let a = prev.next
    • let b = a.next
    • relink pointers to swap a and b
    • move prev to the end of the swapped pair
  4. Return dummy.next.

Correctness

At the start of each iteration:

prev.next

points to the first node of the next unswapped pair.

Let the pair be:

a -> b

The algorithm changes pointers so that:

prev -> b -> a

while preserving the remainder of the list after b.

After relinking, the pair is correctly swapped and connected to both the already-processed prefix and the unprocessed suffix.

Then prev moves to a, which is now the second node of the swapped pair.

So the invariant holds for the next iteration.

If fewer than two nodes remain, no swap is possible, and the remaining nodes are already correctly positioned.

Therefore the algorithm swaps every adjacent pair exactly once and returns the correct modified list.

Complexity

Metric Value Why
Time O(n) Each node is visited once
Space O(1) Only pointer variables are used

Implementation

from typing import Optional

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]:
        dummy = ListNode(0, head)

        prev = dummy

        while prev.next and prev.next.next:
            a = prev.next
            b = a.next

            a.next = b.next
            b.next = a
            prev.next = b

            prev = a

        return dummy.next

Code Explanation

Create the dummy node:

dummy = ListNode(0, head)

This simplifies swaps involving the original head.

prev tracks the node before the pair being swapped:

prev = dummy

Continue while at least two nodes exist:

while prev.next and prev.next.next:

Get the pair:

a = prev.next
b = a.next

Perform the swap.

Connect a to the remainder of the list:

a.next = b.next

Make b point to a:

b.next = a

Connect the previous section to b:

prev.next = b

Move prev forward:

prev = a

Return the real head:

return dummy.next

Testing

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def to_list(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

def run_tests():
    s = Solution()

    head = build_list([1, 2, 3, 4])
    assert to_list(s.swapPairs(head)) == [2, 1, 4, 3]

    head = build_list([])
    assert to_list(s.swapPairs(head)) == []

    head = build_list([1])
    assert to_list(s.swapPairs(head)) == [1]

    head = build_list([1, 2, 3])
    assert to_list(s.swapPairs(head)) == [2, 1, 3]

    head = build_list([1, 2])
    assert to_list(s.swapPairs(head)) == [2, 1]

    print("all tests passed")

run_tests()
Test Why
[1,2,3,4] Standard even-length example
[] Empty list
[1] Single node cannot swap
[1,2,3] Odd number of nodes
[1,2] One pair only