# 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:

```text
1 -> 2 -> 3 -> 4
```

becomes:

```text
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](https://leetcode.com/problems/swap-nodes-in-pairs/?utm_source=chatgpt.com))

## 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:

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

## Examples

Example 1:

```text
head = [1,2,3,4]
```

Swap pairs:

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

Output:

```text
[2,1,4,3]
```

Example 2:

```text
head = []
```

Output:

```text
[]
```

Example 3:

```text
head = [1]
```

A single node has no partner to swap with.

Output:

```text
[1]
```

## First Thought: Swap Values

One possible idea is:

```python
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:

```text
a -> b
```

we need:

```text
b -> a
```

The tricky part is preserving the rest of the list.

Suppose we have:

```text
prev -> a -> b -> next_pair
```

After swapping:

```text
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:

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

After swapping `a` and `b`:

```text
dummy -> 2 -> 1 -> 3 -> 4
```

The next iteration starts from node `1`.

## Visual Walkthrough

Use:

```text
1 -> 2 -> 3 -> 4
```

Create:

```text
dummy -> 1 -> 2 -> 3 -> 4
```

Set:

```text
prev = dummy
```

First pair:

```text
a = 1
b = 2
```

Store:

```text
next_pair = 3
```

Now update pointers.

Step 1:

```text
prev.next = b
```

Result:

```text
dummy -> 2
1 -> 2 -> 3 -> 4
```

Step 2:

```text
b.next = a
```

Result:

```text
dummy -> 2 -> 1
```

Step 3:

```text
a.next = next_pair
```

Result:

```text
dummy -> 2 -> 1 -> 3 -> 4
```

Move:

```text
prev = a
```

Now process:

```text
3 -> 4
```

Final result:

```text
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:

```text
prev.next
```

points to the first node of the next unswapped pair.

Let the pair be:

```text
a -> b
```

The algorithm changes pointers so that:

```text
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

```python
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:

```python
dummy = ListNode(0, head)
```

This simplifies swaps involving the original head.

`prev` tracks the node before the pair being swapped:

```python
prev = dummy
```

Continue while at least two nodes exist:

```python
while prev.next and prev.next.next:
```

Get the pair:

```python
a = prev.next
b = a.next
```

Perform the swap.

Connect `a` to the remainder of the list:

```python
a.next = b.next
```

Make `b` point to `a`:

```python
b.next = a
```

Connect the previous section to `b`:

```python
prev.next = b
```

Move `prev` forward:

```python
prev = a
```

Return the real head:

```python
return dummy.next
```

## Testing

```python
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 |