AlgoMaster Logo

Swap Nodes in Pairs

Last Updated: March 29, 2026

medium
3 min read

Understanding the Problem

We need to take every consecutive pair of nodes in a linked list and swap their positions. So node 1 and node 2 swap, node 3 and node 4 swap, and so on. If the list has an odd number of nodes, the last node stays where it is.

The important constraint here is that we can't just swap values. We have to actually rewire the node pointers. This makes the problem more interesting because swapping two nodes in a linked list requires updating not just the two nodes themselves, but also the node that points to them. If you forget about the previous node's pointer, you'll break the chain.

The key observation is this: for each pair, you need to track three things: the node before the pair (so you can rewire its next), the first node in the pair, and the second node in the pair. A dummy node before the head simplifies the first swap since the head itself has no predecessor.

Key Constraints:

  • 0 <= n <= 100 → With at most 100 nodes, any approach from O(n) to O(n^2) is fine. This is a small input size, so the focus is on correctness and clean pointer manipulation, not performance.
  • 0 <= Node.val <= 100 → Values are non-negative integers. Not relevant to the algorithm since we're manipulating pointers, not values.
  • Cannot modify node values → This rules out the easy shortcut of just swapping .val between adjacent nodes. We must physically rearrange the nodes.

Approach 1: Recursive

Intuition

The recursive approach breaks the problem into a beautifully simple subproblem. Here's the idea: if we have at least two nodes, we swap the first two, then recursively handle the rest of the list. The base case is when there are fewer than two nodes remaining, in which case nothing needs to happen.

The "aha moment" is realizing that after swapping nodes 1 and 2, node 1 (now in the second position) should point to the result of recursively swapping the rest of the list starting from node 3. This naturally chains all the swaps together.

Algorithm

  1. If the list is empty or has only one node, return the head as-is (base case).
  2. Let first = head and second = head.next.
  3. Recursively swap the sublist starting from second.next (the third node onward).
  4. Set first.next to the result of the recursive call.
  5. Set second.next to first.
  6. Return second as the new head of this swapped pair.

Example Walkthrough

1Initial: first=1, second=2
first
1
2
second
3
4
null
1/4

Code

This approach works correctly but uses O(n) stack space. Can we swap pairs iteratively using a pointer that walks through the list, eliminating the recursion stack entirely?

Approach 2: Iterative with Dummy Node

Intuition

The iterative approach processes pairs from left to right using a pointer that tracks the node just before each pair. Here's the trick: we create a dummy node that points to the head. This dummy acts as the "previous" node for the first pair, which elegantly handles the edge case of updating the head pointer.

For each pair, we need to do three pointer rewirings:

  1. The previous node's next should point to the second node (which becomes the new first in the pair).
  2. The first node's next should point to whatever comes after the pair.
  3. The second node's next should point to the first node.

After the swap, the first node (which is now in the second position) becomes the "previous" node for the next pair. This is a subtle but important detail that many people get wrong.

Algorithm

  1. Create a dummy node with dummy.next = head.
  2. Initialize prev = dummy.
  3. While prev.next and prev.next.next are not null (there's a complete pair):
    • Let first = prev.next and second = prev.next.next.
    • Rewire: prev.next = second, first.next = second.next, second.next = first.
    • Advance: prev = first (first is now in the second position of the swapped pair).
  4. Return dummy.next.

Example Walkthrough

1Initialize: dummy → 1 → 2 → 3 → 4, prev = dummy
first
1
2
second
3
4
null
1/4

Code