LeetCode 24 - Swap Nodes in Pairs

Difficulty: 🟡 Medium
Topics: Linked List, Recursion

Solution

Problem Understanding

The problem gives us the head of a singly linked list and asks us to swap every pair of adjacent nodes. The important detail is that we are not allowed to modify the values stored inside the nodes. We must physically rearrange the node connections by changing pointers.

For example, if the linked list is:

1 -> 2 -> 3 -> 4

after swapping adjacent pairs, it becomes:

2 -> 1 -> 4 -> 3

The first two nodes are swapped, then the next two nodes are swapped, and so on.

If the list contains an odd number of nodes, the final node remains in its original position because it has no partner to swap with. For example:

1 -> 2 -> 3

becomes:

2 -> 1 -> 3

The input represents the head pointer of a singly linked list. Each node contains an integer value and a pointer to the next node. The output should be the head of the modified linked list after all adjacent swaps have been completed.

The constraints are relatively small, with at most 100 nodes, so performance is not difficult from a raw complexity perspective. However, the challenge is pointer manipulation. Linked list problems are often less about asymptotic complexity and more about correctly handling references without losing access to parts of the list.

Several edge cases are important:

The list may be empty.
The list may contain only one node.
The list may contain an odd number of nodes.
The list may contain exactly two nodes.
Incorrect pointer updates can create cycles or disconnect nodes from the list.

Because the problem forbids modifying node values, solutions that simply swap values are invalid even though they would appear easier.

Approaches

Brute Force Approach

A straightforward but invalid conceptual approach would be to swap the values inside adjacent nodes instead of rearranging the nodes themselves.

For example:

1 -> 2 -> 3 -> 4

could become:

2 -> 1 -> 4 -> 3

by exchanging the integer values stored in each pair of nodes.

This approach works logically because the visible sequence appears correct. However, the problem explicitly states that node values cannot be modified. Only the node connections themselves may change.

Even though this approach runs in linear time and constant space, it violates the problem requirements.

Another brute force style approach would be to copy all nodes into an array, swap positions inside the array, and then rebuild the linked list connections. This works correctly, but it uses unnecessary extra memory.

Optimal Approach

The key observation is that swapping two adjacent nodes in a singly linked list only requires changing a few pointers.

Suppose we have:

prev -> A -> B -> nextPair

After swapping A and B, we want:

prev -> B -> A -> nextPair

This can be done with three pointer updates:

A.next = B.next
B.next = A
prev.next = B

To simplify handling the head of the list, we use a dummy node placed before the original head. This avoids special-case logic when swapping the first pair.

We then iterate through the list two nodes at a time, swapping pairs until fewer than two nodes remain.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Copy nodes into an array and rebuild connections
Optimal	O(n)	O(1)	Swap nodes directly using pointer manipulation

Algorithm Walkthrough

Create a dummy node whose next pointer points to the original head of the list. This dummy node helps handle swaps at the beginning of the list uniformly.
Initialize a pointer called prev to the dummy node. This pointer always represents the node immediately before the pair currently being swapped.
Continue processing while there are at least two nodes available to swap. Specifically, check that both prev.next and prev.next.next exist.
Identify the two nodes in the current pair:

first = prev.next
second = first.next

Save the node that comes after the pair:

next_pair = second.next

Reverse the pair by changing pointers:

Point second.next to first
Point first.next to next_pair

Connect the previous portion of the list to the swapped pair:

prev.next = second

Move prev forward to first, which is now the second node in the swapped pair.
Repeat until no complete pair remains.
Return dummy.next, which points to the new head after all swaps.

Why it works

At every iteration, the algorithm maintains the invariant that all nodes before prev have already been correctly swapped and connected. The current pair is isolated and rearranged without losing access to the remaining list because next_pair is stored before any pointer modifications occur. Since each pair is swapped exactly once and all connections are restored correctly, the final linked list contains all original nodes in the required order.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head

        prev = dummy

        while prev.next and prev.next.next:
            first = prev.next
            second = first.next

            # Save the start of the next pair
            next_pair = second.next

            # Swap the current pair
            second.next = first
            first.next = next_pair
            prev.next = second

            # Move prev to the end of the swapped pair
            prev = first

        return dummy.next

The implementation starts by creating a dummy node. This simplifies edge cases because the head of the list may change after the first swap.

The prev pointer tracks the node immediately before the current pair. During each loop iteration, the algorithm identifies the two nodes being swapped as first and second.

Before modifying any pointers, the code stores second.next inside next_pair. This prevents losing access to the remainder of the linked list.

The swap itself occurs through three pointer updates:

second.next = first
first.next = next_pair
prev.next = second

After the swap, first becomes the second node in the pair, so prev advances to first for the next iteration.

Finally, dummy.next is returned because the original head may no longer be the actual head after swapping.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}

    prev := dummy

    for prev.Next != nil && prev.Next.Next != nil {
        first := prev.Next
        second := first.Next

        // Save the start of the next pair
        nextPair := second.Next

        // Swap the pair
        second.Next = first
        first.Next = nextPair
        prev.Next = second

        // Move prev forward
        prev = first
    }

    return dummy.Next
}

The Go implementation follows the same pointer manipulation logic as the Python version. The primary difference is Go's explicit pointer syntax using *ListNode.

Go uses nil instead of Python's None. Since linked lists are pointer-based structures in Go, the implementation naturally manipulates node references directly without additional language-specific complications.

No integer overflow concerns exist because node values are never modified or involved in arithmetic operations.

Worked Examples

Example 1

Input:

1 -> 2 -> 3 -> 4

Initial state:

Variable	Value
dummy	0
prev	dummy
list	0 -> 1 -> 2 -> 3 -> 4

First Iteration

Variable	Value
first	1
second	2
next_pair	3

Perform swap:

2.next = 1
1.next = 3
dummy.next = 2

List becomes:

0 -> 2 -> 1 -> 3 -> 4

Move prev to 1.

Second Iteration

Variable	Value
first	3
second	4
next_pair	null

Perform swap:

4.next = 3
3.next = null
1.next = 4

List becomes:

0 -> 2 -> 1 -> 4 -> 3

Return:

2 -> 1 -> 4 -> 3

Example 2

Input:

[]

The head is null, so the loop condition fails immediately.

Return:

[]

Example 3

Input:

1

There is only one node, so no pair exists to swap.

Return:

1

Example 4

Input:

1 -> 2 -> 3

First Iteration

Swap 1 and 2.

List becomes:

2 -> 1 -> 3

Now only one node remains at the end, so the loop stops.

Return:

2 -> 1 -> 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited a constant number of times
Space	O(1)	Only a few pointers are used regardless of input size

The algorithm processes the linked list in a single pass. Every iteration swaps exactly one pair, and each node participates in at most one swap operation. Since only a fixed number of pointer variables are maintained, the extra memory usage remains constant.

Test Cases

# Definition for testing
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

class Solution:
    def swapPairs(self, head):
        dummy = ListNode(0)
        dummy.next = head

        prev = dummy

        while prev.next and prev.next.next:
            first = prev.next
            second = first.next

            next_pair = second.next

            second.next = first
            first.next = next_pair
            prev.next = second

            prev = first

        return dummy.next

solution = Solution()

# Empty list
assert to_list(solution.swapPairs(build_list([]))) == []

# Single node
assert to_list(solution.swapPairs(build_list([1]))) == [1]

# Two nodes
assert to_list(solution.swapPairs(build_list([1, 2]))) == [2, 1]

# Even number of nodes
assert to_list(solution.swapPairs(build_list([1, 2, 3, 4]))) == [2, 1, 4, 3]

# Odd number of nodes
assert to_list(solution.swapPairs(build_list([1, 2, 3]))) == [2, 1, 3]

# Longer odd-length list
assert to_list(solution.swapPairs(build_list([1, 2, 3, 4, 5]))) == [2, 1, 4, 3, 5]

# Longer even-length list
assert to_list(solution.swapPairs(build_list([1, 2, 3, 4, 5, 6]))) == [2, 1, 4, 3, 6, 5]

# Duplicate values
assert to_list(solution.swapPairs(build_list([7, 7, 7, 7]))) == [7, 7, 7, 7]

# Maximum small-style stress case
assert to_list(solution.swapPairs(build_list(list(range(10))))) == [1, 0, 3, 2, 5, 4, 7, 6, 9, 8]

Test	Why
`[]`	Validates empty list handling
`[1]`	Validates single-node edge case
`[1,2]`	Smallest swappable pair
`[1,2,3,4]`	Standard even-length case
`[1,2,3]`	Standard odd-length case
`[1,2,3,4,5]`	Ensures final unmatched node remains unchanged
`[1,2,3,4,5,6]`	Multiple swaps across entire list
`[7,7,7,7]`	Ensures algorithm swaps nodes, not values
`range(10)`	Larger stress-style validation

Edge Cases

Empty List

An empty list is represented by head = None. This case can easily cause null pointer errors if the implementation assumes at least one node exists.

The solution handles this safely because the loop condition checks:

while prev.next and prev.next.next:

If prev.next is None, the loop never executes, and the function immediately returns dummy.next, which is also None.

Single Node List

A list with only one node cannot form a pair, so no swap should occur.

This case is tricky because implementations that blindly access head.next may crash. The loop condition prevents this by requiring two consecutive nodes before entering the swap logic.

The original node is returned unchanged.

Odd Number of Nodes

When the list length is odd, the final node has no adjacent partner and must remain in place.

For example:

1 -> 2 -> 3 -> 4 -> 5

becomes:

2 -> 1 -> 4 -> 3 -> 5

The algorithm naturally handles this because the loop only runs when two nodes are available. Once only one node remains, the condition fails and the last node stays connected exactly where it should.