LeetCode 24: Swap Nodes in Pairs

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. (leetcode.com)

Input and Output

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

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