Swap Nodes in Pairs

How it works

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.

Steps

1. Create a dummy node pointing to the head, and initialize prev to dummy and curr to head.
2. 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.
3. Return dummy.next.

Complexity

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

Things to watch for

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.

from typing import Optional

# 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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(0, head);
        ListNode* prev = &dummy, *curr = head;

        while (curr && curr->next) {
            ListNode* nxtPair = curr->next->next;
            ListNode* second = curr->next;

            // Reverse this pair
            second->next = curr;
            curr->next = nxtPair;
            prev->next = second;

            // Update pointers
            prev = curr;
            curr = nxtPair;
        }

        return dummy.next;
    }
};