Swap Nodes in Pairs

Problem

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (only nodes themselves may be changed).

Visual Example

Input:  1 -> 2 -> 3 -> 4 -> NULL
Output: 2 -> 1 -> 4 -> 3 -> NULL

Step-by-Step Visualization

Initial State

curr
 |
 v
[1] --> [2] --> [3] --> [4] --> NULL
         |
         v
      new_head

prev = NULL

Key Insight

For each pair, we need to:

1. Make the second node point to the first
2. Make the first node point to what comes after the pair
3. Connect the previous pair to the new first node (which was the second)

Iteration 1: Swap nodes 1 and 2

Loop condition: curr=[1], curr.next=[2] ✓

Step 1: if prev: → prev is NULL, skip this step

Step 2: prev = curr (prev now points to node 1)

prev
curr
 |
 v
[1] --> [2] --> [3] --> [4] --> NULL
         |
         v
      new_head

Step 3: next_node = curr.next.next (save node 3)

prev             next_node
curr                 |
 |                   v
 v
[1] --> [2] --> [3] --> [4] --> NULL
         |
         v
      new_head

Step 4: curr.next.next = curr (node 2 now points to node 1)

        new_head
           |
           v
          [2]
           |
     +-----+
     |
     v
    [1] ---------> [3] --> [4] --> NULL
     ^              ^
     |              |
    prev        next_node
    curr

Pointer state:
  [1].next = [2]  (unchanged from before)
  [2].next = [1]  (CHANGED - was [3])

Note: [1] and [2] form a cycle: [1] -> [2] -> [1] -> ...

Step 5: curr.next = next_node (node 1 now points to node 3, breaking cycle)

      new_head
         |
         v
        [2]
         |
         v
        [1] ---------> [3] --> [4] --> NULL
         ^              ^
         |              |
       prev         next_node
       curr

Pointer state:
  [1].next = [3]  (CHANGED - was [2], breaks cycle)
  [2].next = [1]  (from step 4)

Traversal from new_head: [2] -> [1] -> [3] -> [4] -> NULL

Step 6: curr = next_node (move curr to node 3)

new_head  prev       curr
   |       |          |
   v       v          v
  [2] --> [1] --> [3] --> [4] --> NULL

Iteration 2: Swap nodes 3 and 4

Loop condition: curr=[3], curr.next=[4] ✓

Step 1: if prev: → prev is [1], execute: prev.next = curr.next

new_head  prev       curr
   |       |          |
   v       v          v
  [2] --> [1]        [3] --> [4] --> NULL
           |                  ^
           +------------------+

Pointer state:
  [1].next = [4]  (CHANGED - was [3])

Note: [3] is now only reachable via curr pointer, not from prev

Step 2: prev = curr (prev now points to node 3)

new_head           prev
                   curr
   |                |
   v                v
  [2] --> [1]      [3] --> [4] --> NULL
           |                ^
           +----------------+

Step 3: next_node = curr.next.next (save NULL)

next_node = [4].next = NULL

Step 4: curr.next.next = curr (node 4 now points to node 3)

new_head           prev
                   curr
   |                |
   v                v
  [2] --> [1]      [3] <--> [4]
           |        ^
           +--------+

Pointer state:
  [3].next = [4]  (unchanged)
  [4].next = [3]  (CHANGED - was NULL)

Note: [3] and [4] form a cycle: [3] -> [4] -> [3] -> ...
      [1] still points to [4], so: [1] -> [4] -> [3] -> [4] -> ...

Step 5: curr.next = next_node (node 3 now points to NULL, breaking cycle)

new_head           prev
                   curr
   |                |
   v                v
  [2] --> [1] --> [4] --> [3] --> NULL

Pointer state:
  [3].next = NULL  (CHANGED - was [4], breaks cycle)
  [4].next = [3]   (from step 4)
  [1].next = [4]   (from step 1)

Traversal from new_head: [2] -> [1] -> [4] -> [3] -> NULL

Step 6: curr = next_node = NULL, loop exits

Final Result

new_head
   |
   v
  [2] --> [1] --> [4] --> [3] --> NULL

Algorithm Pattern

For each pair where curr = A, curr.next = B, and C = B.next:

    Before:  ... --> prev_node --> A --> B --> C --> ...
    After:   ... --> prev_node --> B --> A --> C --> ...

    Operations (in code order):
    1. prev_node.next = B   (connect previous pair to B) [skip if first pair]
    2. prev = A             (save A as prev for next iteration)
    3. next_node = C        (save C before we lose access)
    4. B.next = A           (B points to A - creates temporary cycle!)
    5. A.next = C           (A points to C - breaks the cycle)
    6. curr = C             (move to next pair)

Edge Cases

Empty list:     NULL              --> NULL
Single node:    [1] --> NULL      --> [1] --> NULL
Two nodes:      [1] --> [2] --> NULL --> [2] --> [1] --> NULL
Odd length:     [1] --> [2] --> [3] --> NULL --> [2] --> [1] --> [3] --> NULL
                                                          (last node stays in place)

Code Template

def solution(head: Optional[ListNode]) -> Optional[ListNode]:
    # Edge case: empty or single node
    if not head or not head.next:
        return head

    curr = head
    new_head = head.next  # Second node becomes new head
    prev = None

    while curr and curr.next:
        # Connect previous pair's tail to current pair's second node
        if prev:
            prev.next = curr.next

        # IMPORTANT: Save curr as prev BEFORE modifying pointers
        # (curr will become the tail of this swapped pair)
        prev = curr

        # Save the node after the pair (before we lose access to it)
        next_node = curr.next.next

        # Swap: make second point to first (creates temporary cycle!)
        curr.next.next = curr

        # Break the cycle: first now points to the rest of the list
        curr.next = next_node

        # Move to next pair
        curr = next_node

    return new_head

Complexity

• Time: O(n) - single pass through the list
• Space: O(1) - only using a few pointers

Common Mistakes

1. Forgetting to save new_head - The second node becomes the new head
2. Not handling odd-length lists - Last node has no pair, stays in place
3. Losing connection between pairs - Must connect prev to the new first of each pair
4. Off-by-one in pointer updates - Order of operations matters!

Recursive Alternative

def solution(head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return head

    # new_head is the second node (will be first after swap)
    new_head = head.next

    # Recursively swap the rest, connect to first node
    head.next = solution(new_head.next)

    # Complete the swap
    new_head.next = head

    return new_head

Recursive visualization:

swap([1,2,3,4])
  new_head = [2]
  [1].next = swap([3,4])
               new_head = [4]
               [3].next = swap(NULL) = NULL
               [4].next = [3]
               return [4]
           = [4] --> [3] --> NULL
  [2].next = [1]
  return [2] --> [1] --> [4] --> [3] --> NULL