Generated by Codex with GPT-5

Quick facts

  • Difficulty: MEDIUM
  • Problem: Swap Nodes in Pairs
  • Main tags: Linked List, Recursion, Iteration, Pointer Manipulation

What the problem is really asking

The input is the head of a singly linked list. Every adjacent pair of nodes must be swapped:

  • 1 -> 2 -> 3 -> 4 becomes 2 -> 1 -> 4 -> 3
  • 1 -> 2 -> 3 becomes 2 -> 1 -> 3

The important constraint is that node values cannot be copied around. The solution has to rewire the list itself.

That makes this a pointer-management problem, not a value-swapping problem. The real task is to repeatedly transform this local pattern:

previous -> first -> second -> rest

into:

previous -> second -> first -> rest

Once that local rewrite is understood, the whole problem becomes a loop over the list.

The simplest correct idea

The cleanest first explanation is recursive.

If the list has fewer than two nodes, there is nothing to swap, so the current head is already correct.

Otherwise, let:

  • first be the current head
  • second be head.next

The first pair should become second -> first. After that, the rest of the list should also be swapped in pairs, so first.next can point to the recursively processed remainder.

That gives a very small and elegant solution:

  • swap the first two nodes
  • recursively solve the remaining list
  • connect the pieces

It is correct and easy to derive, but it uses O(n) call stack space in the worst case.

Why the iterative solution is the optimal one

The iterative version performs the same local swap without recursive overhead.

The best tool here is a dummy head node placed before the real head. That dummy node is useful because after swapping the first pair, the head of the list changes. With a dummy node, the code can treat the first pair exactly the same as every later pair instead of handling it as a special case.

At each step, only four references matter:

  • node_before_pair
  • first_node
  • second_node
  • pair_successor

If the list currently looks like:

node_before_pair -> first_node -> second_node -> pair_successor

then the correct rewiring is:

  1. point node_before_pair.next to second_node
  2. point second_node.next to first_node
  3. point first_node.next to pair_successor

After that, the pair has been swapped, and first_node becomes the tail of the processed pair. So the loop moves node_before_pair forward to first_node and repeats on the next pair.

This handles all cases naturally:

  • an empty list stays empty
  • a one-node list stays unchanged
  • an odd final node is left in place because there is no partner to swap with

How to derive the pointer rewiring

The easiest way to avoid mistakes is to think in terms of preserving access to the remainder of the list.

Before any pointer changes happen, pair_successor = second_node.next must be saved. Otherwise the rest of the list could become unreachable after the swap starts.

Once that saved reference exists, the swap is just a local permutation:

  • the previous part of the list should now point to the second node
  • the second node should point back to the first node
  • the first node should point to whatever originally came after the pair

That is why the solution can be written as a short loop. Each iteration only touches a constant number of pointers, and no node is ever processed more than once.

Why the algorithm is correct

The key invariant is:

before each loop iteration, everything before node_before_pair has already been swapped correctly, and node_before_pair.next is the first node of the next untouched segment.

Initially this is true because the dummy head is placed before the entire list, so nothing has been processed yet.

During one iteration, the algorithm swaps exactly the next two nodes and reconnects that swapped pair to both the processed prefix and the untouched suffix. No other part of the list is changed. After the swap, node_before_pair moves to the tail of the newly processed pair, so the invariant is restored for the next iteration.

When the loop stops, fewer than two untouched nodes remain. That means the algorithm has swapped every possible adjacent pair and left any final unmatched node unchanged, which is exactly what the problem requires.

Best approaches

There are two strong answers:

  • The recursive solution is the easiest first solution to explain. It is compact and directly mirrors the problem structure, but it uses O(n) extra stack space.
  • The iterative dummy-head solution is the best final answer. It keeps the same O(n) running time while reducing extra space to O(1).

For an interview, a good progression is to mention the recursive idea first, then explain that the same local swap can be performed iteratively with constant extra space.

  • Time: O(n)
  • Extra space: O(1) for the iterative version

Python solution

The implementation below uses the optimal iterative approach. LeetCode provides the ListNode class, so the code focuses on the pair-swapping logic itself. The helper function keeps the pointer manipulation isolated and makes the Solution entry point trivial.

from typing import Optional


def swap_adjacent_pairs(head: Optional["ListNode"]) -> Optional["ListNode"]:
    """
    Swap every two adjacent nodes in-place and return the new head.
    """
    if head is None or head.next is None:
        return head

    dummy_head = ListNode(0, head)
    node_before_pair = dummy_head

    while node_before_pair.next is not None and node_before_pair.next.next is not None:
        first_node = node_before_pair.next
        second_node = first_node.next
        pair_successor = second_node.next

        # Rewire the current window:
        # node_before_pair -> first_node -> second_node -> pair_successor
        # becomes
        # node_before_pair -> second_node -> first_node -> pair_successor
        node_before_pair.next = second_node
        second_node.next = first_node
        first_node.next = pair_successor

        # first_node is now the tail of the processed pair.
        node_before_pair = first_node

    return dummy_head.next


class Solution:
    def swapPairs(self, head: Optional["ListNode"]) -> Optional["ListNode"]:
        """LeetCode entry point."""
        return swap_adjacent_pairs(head)

Interview follow-ups

Could the same problem be solved recursively?

Yes. The recursive version treats the first two nodes as one local decision and delegates the rest of the work to the remainder of the list. If the list has zero or one node, it returns immediately. Otherwise it stores second = head.next, recursively swaps the list starting at second.next, attaches that result after head, and returns second as the new head of the current segment. This works because each call solves the same problem on a strictly smaller suffix, and the local pair swap is independent once the recursive result for the remainder is known. The time complexity stays O(n), but the call stack grows to O(n), which is why the iterative version is preferred for the final answer.

How would this generalize to swapping or reversing nodes in groups of k?

The standard generalization is to look ahead k nodes and only process the block if all k nodes exist. Once a full block is confirmed, that block can be reversed in-place and reconnected to the previous processed segment and the next untouched segment. This works because the linked list can be partitioned into independent contiguous blocks: each block can be transformed locally as long as the code preserves the boundary pointers before rewiring begins. The overall running time remains O(n), and an iterative solution can still use O(1) extra space, but the bookkeeping becomes more involved because each step must manage block boundaries instead of a single adjacent pair.

Can this be done without a dummy head node?

Yes, but the code becomes more brittle. Without a dummy head, the first swapped pair produces the new head of the list, so the implementation has to special-case that first update before it can enter a regular loop for later pairs. After that, it still needs a pointer to the tail of the previously processed pair in order to reconnect the list correctly. The algorithm is still O(n) time and O(1) extra space, and it works for the same reason as the dummy-head version, but the dummy node is usually the cleaner interview answer because it removes the hardest edge case and makes every iteration follow the same pointer pattern.