Swap Nodes in Pairs

Given the head of a singly linked list, swap every two adjacent nodes: the 1st with the 2nd, the 3rd with the 4th, and so on. If the list has an odd length, the final node has no partner and stays where it is. Return the head of the rearranged list.

You must rearrange the nodes themselves by changing next pointers; overwriting the val fields is not allowed.

The list is shown as an array of its values from head to tail, e.g. [5, 6, 7].

Example 1

Example 2

Example 3

Constraints

• The number of nodes is in the range [0, 104]
• 0 <= Node.val <= 100

Pattern Path · Linked Lists · problem 72 of 169

Start simple

Copy the values into an array, swap neighbours there and build a new list: O(n) time but O(n) extra space, and it does not move the original nodes.

The key idea

Swapping a pair a → b inside a list touches exactly three links: the node before the pair must point to b, b must point to a, and a must point to whatever came after b. Get those three right and the rest of the list is untouched.

Put a dummy node in front of the head so that the first pair also has a predecessor. With prev = dummy, while prev.next and prev.next.next both exist: let a = prev.next and b = a.next, then set a.next = b.next, b.next = a, prev.next = b. After the swap a is the second node of the pair, so it becomes the new prev. The loop stops when fewer than two nodes remain, which leaves an odd tail node in place.

The order of the three assignments matters: saving b.next into a.next first means you never lose the rest of the list. A recursive version (swap the first pair, recurse on the rest) is shorter but uses O(n) stack.

Complexity

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

Python

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev = dummy
        while prev.next and prev.next.next:
            a, b = prev.next, prev.next.next
            a.next = b.next  # a now points past the pair
            b.next = a       # b comes first
            prev.next = b    # attach the swapped pair to what came before
            prev = a         # a is the second node of the pair now
        return dummy.next

JavaScript

var swapPairs = function(head) {
  const dummy = new ListNode(0, head);
  let prev = dummy;
  while (prev.next && prev.next.next) {
    const a = prev.next, b = prev.next.next;
    a.next = b.next; // a now points past the pair
    b.next = a;      // b comes first
    prev.next = b;   // attach the swapped pair to what came before
    prev = a;        // a is the second node of the pair now
  }
  return dummy.next;
};

What the interviewer is checking

This is a pointer-manipulation drill: the interviewer watches whether you rewire links in a safe order, use a dummy head, and handle odd lengths and empty input.

Mistakes to avoid

• Forgetting to reconnect the previous pair to the new first node of the current pair, which drops nodes.
• Losing the rest of the list by overwriting b.next before saving it.
• Returning the old head, which is now the second node.

Follow-ups to expect

• Reverse the list in groups of k. (Generalise the rewiring per group.)
• Do it recursively. (Swap first pair, recurse on rest.)
• Swap pairs in a doubly linked list. (Also fix the prev pointers.)

In real software

Byte-order conversion swaps adjacent units in a buffer, and rearranging entries in an intrusive linked list (as kernels and allocators use) is done by relinking nodes rather than copying their payloads.

Practice next