24. Swap Nodes In Pairs - Explanation

1. Convert To Array

Intuition

The simplest approach is to convert the linked list to an array, where swapping elements is straightforward using index-based access. Once we swap adjacent elements in the array, we rebuild the linked list connections. This trades space efficiency for implementation simplicity.

Algorithm

Traverse the linked list and store all nodes in an array.
Iterate through the array in steps of 2, swapping adjacent elements.
Reconnect all nodes by setting each node's next pointer to the following node in the array.
Set the last node's next to null and return the first element as the new head.

# Definition for singly-linked list.
# 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]:
        if not head:
            return None
        arr = []
        cur = head

        while cur:
            arr.append(cur)
            cur = cur.next

        for i in range(0, len(arr) - 1, 2):
            arr[i], arr[i + 1] = arr[i + 1], arr[i]

        for i in range(len(arr) - 1):
            arr[i].next = arr[i + 1]

        arr[-1].next = None
        return arr[0]

Time & Space Complexity

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

2. Recursion

Intuition

We can think of the problem recursively: swap the first two nodes, then let recursion handle the rest. The first node should point to the result of swapping the remaining list (starting from the third node). The second node becomes the new head of this pair and points to the first node. This recursive structure naturally handles lists of any length.

Algorithm

Base case: if the list is empty or has only one node, return the head as-is.
Save references to the first node (cur) and second node (nxt).
Recursively swap the sublist starting from the third node and connect it to cur.
Point nxt to cur.
Return nxt as the new head of this swapped pair.

# Definition for singly-linked list.
# 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]:
        if not head or not head.next:
            return head

        cur = head
        nxt = head.next
        cur.next = self.swapPairs(nxt.next)
        nxt.next = cur
        return nxt

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

3. Iteration

Intuition

We can swap pairs in place by carefully managing pointers. A dummy node simplifies handling the head change. For each pair, we need to: save the reference to the next pair, reverse the current pair's pointers, and connect the previous node to the new first node of the swapped pair. Moving two nodes at a time ensures we process each pair exactly once.

Algorithm

Create a dummy node pointing to the head, and initialize prev to dummy and curr to head.
While curr and curr.next both exist:
- Save the start of the next pair: nxtPair = curr.next.next.
- Identify the second node in the pair.
- Reverse the pair: point second to first, first to the next pair.
- Connect previous node to the new first (second node).
- Update prev to be curr and move curr to nxtPair.
Return dummy.next.

# Definition for singly-linked list.
# 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, curr = dummy, head

        while curr and curr.next:
            nxtPair = curr.next.next
            second = curr.next

            # Reverse this pair
            second.next = curr
            curr.next = nxtPair
            prev.next = second

            # Update pointers
            prev = curr
            curr = nxtPair

        return dummy.next

Time & Space Complexity

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

Common Pitfalls

Losing Reference to the Next Pair

When swapping a pair of nodes, you must save a reference to the node after the pair (curr.next.next) before modifying any pointers. If you swap the current pair first, curr.next changes and you lose access to the remaining list. Always store nxtPair = curr.next.next at the beginning of each iteration.

Forgetting to Update the Previous Node's Next Pointer

After swapping a pair, the previous node (or dummy node for the first pair) must point to the new first node of the swapped pair. A common mistake is correctly swapping the pair internally but failing to connect it back to the rest of the list, resulting in a broken chain or lost nodes.

Not Handling Odd-Length Lists

When the list has an odd number of nodes, the last node has no partner to swap with and should remain in place. Your loop condition must check that both curr and curr.next exist before attempting a swap. Failing to check both conditions can cause null pointer exceptions or incorrect behavior on the final unpaired node.