Swap Nodes in Pairs

A value swap can produce the right sequence while violating the contract. The real task is to move node identities by changing links—and to do it without losing the untouched suffix.

The iterative Swap Nodes in Pairs solution is a small local transformation:

1. Identify the node before the pair.
2. Capture the two nodes and the remainder.
3. Perform three next assignments.
4. Advance to the new tail of the swapped pair.

That pattern is more reliable than trying to “reverse the pair” by intuition. Every pointer has a job, and every assignment preserves a specific connection.

The contract and the local pattern

For each adjacent pair:

• The first node must move behind the second.
• Node values must remain unchanged.
• The rest of the list must remain reachable.
• If one node is left at the end, it stays where it is.
• An empty list is valid.
• The function returns the new head, which may differ from the original head.

For example:

1 → 2 → 3 → 4

must become:

2 → 1 → 4 → 3

For an odd-length list:

1 → 2 → 3

the result is:

2 → 1 → 3

The recognition cue is local structure. Each iteration transforms exactly two nodes and leaves the suffix untouched until a later iteration. This is in-place pointer rewiring, not a traversal problem involving a midpoint, a cycle, or unequal pointer speeds. Fast & Slow Pointers are unnecessary here because there is no need to find the middle or compare traversal rates.

A value-based approach might swap 1 and 2 inside their nodes. It can appear correct when you print the list, but it changes data rather than node positions. Interview problems that explicitly require node swaps are testing whether you can preserve object identity and manipulate the structure itself.

Name the pointers before changing links

Pointer bugs usually begin with vague state. Before mutating anything, name the four pieces of the local shape:

pre → first → second → remainder

Each name answers a different obligation:

Pointer	Responsibility
pre	Connects the already-processed prefix to the current pair
first	The node that currently comes first
second	The node that must become first
remainder	The suffix after the current pair

After swapping, the local shape must be:

pre → second → first → remainder

The remainder pointer matters because linked-list mutation destroys access if you overwrite a link too early. Consider this line:

first.next = second.next

If you have not saved second.next, you may still be able to reach the suffix through first.next—but your next assignment might overwrite that path before you use it. The list is a chain of ownership. Break a link without preserving its destination, and the suffix can become orphaned. Point the wrong node backward, and you can create a cycle.

The safe approach is mechanical:

pre        = ...
first      = ...
second     = ...
remainder  = second.next

Capture the local state first. Mutate second.

Derive the iterative rewiring sequence

A dummy node gives the first pair a predecessor just like every later pair:

dummy → head

Without it, the first swap needs special handling because the original head must change from first to second. With a dummy node, every pair follows the same shape:

pre → first → second → remainder

The loop should continue only while two nodes are available:

while pre.next and pre.next.next:

Inside the loop:

first = pre.next
second = first.next
remainder = second.next

Now derive the three rewires.

1. Connect the prefix to the second node

pre.next = second

The processed prefix now enters the pair through its new first node.

pre → second
       ↑
     first

The old first → second connection still exists, so we have not lost either node.

2. Connect the first node to the untouched suffix

first.next = remainder

The node that moves to the back of the pair now points beyond the pair.

pre → second    first → remainder
       ↑         |
       └─────────┘

The diagram is crowded because second.next has not been changed yet, but the important fact is that first has a safe exit to the suffix.

3. Connect the second node to the first

second.next = first

The pair is now complete:

pre → second → first → remainder

Finally, advance pre to first:

pre = first

first is now the tail of the processed prefix. Its next pointer begins the untouched suffix, so the next iteration naturally starts there.

The complete local algorithm is therefore:

dummy → head

while two nodes remain:
    capture first, second, remainder
    connect pre to second
    connect first to remainder
    connect second to first
    move pre to first

This is constant-size work per pair. No array of nodes, copied list, or value buffer is needed.

The invariant that makes the solution safe

An invariant is the statement that remains true at the start of every loop iteration.

dummy.next through pre is already correctly pair-swapped. pre is the tail of that processed prefix, and pre.next begins the untouched suffix.

Initially, the processed prefix is empty. The dummy node points to the original head, so the invariant holds.

Assume the invariant holds at the start of an iteration. The loop guard guarantees that pre.next and pre.next.next both exist, so a complete pair is available:

pre → first → second → remainder

The three rewires produce:

pre → second → first → remainder

This does two things at once:

• It puts the current pair in the required order.
• It reconnects the processed prefix to the untouched suffix.

Then pre = first makes the new tail the boundary between processed and unprocessed nodes. The invariant is restored.

When the loop stops, fewer than two nodes remain after pre. That suffix is already correct: it is either empty or a single unpaired node. No mutation is needed.

The invariant is the difference between code that happens to pass 1 → 2 → 3 → 4 and code you can defend under interview pressure.

Dry-run the pointer state

Take this list:

1 → 2 → 3 → 4

Initially:

dummy → 1 → 2 → 3 → 4
pre = dummy

First iteration

Before mutation:

pre       = dummy
first     = 1
second    = 2
remainder = 3

The rewires are:

pre.next = second       # dummy → 2
first.next = remainder  # 1 → 3
second.next = first     # 2 → 1

The list is now:

dummy → 2 → 1 → 3 → 4

Advance:

pre = first

So:

pre = 1

The processed prefix is 2 → 1, and pre.next points to 3, the untouched suffix.

Second iteration

Before mutation:

pre       = 1
first     = 3
second    = 4
remainder = None

Apply the same three assignments:

pre.next = second       # 1 → 4
first.next = remainder  # 3 → None
second.next = first     # 4 → 3

Now:

dummy → 2 → 1 → 4 → 3

The loop stops because there are no nodes after 3. Returning dummy.next gives 2, the new head.

Odd length

For:

1 → 2 → 3

the first iteration produces:

2 → 1 → 3

Then pre is 1. The loop checks:

pre.next       # 3, exists
pre.next.next  # None

The condition fails. Node 3 remains untouched, exactly as required.

Empty and one-node lists

For an empty list:

dummy → None

For a one-node list:

dummy → 1 → None

In both cases, the loop guard fails immediately. dummy.next returns the original structure.

Exactly one pair

For:

1 → 2

the pair becomes:

2 → 1

This is the case that exposes why dummy.next matters. The original head points to 1, but the resulting head is 2. Returning the original head would return the wrong node.

Python implementation

Assuming the usual ListNode interface with val and next fields, the interview-ready implementation is:

from typing import Optional


class Solution:
    def swapPairs(self, head: Optional["ListNode"]) -> Optional["ListNode"]:
        dummy = ListNode(0, head)
        pre = dummy

        while pre.next and pre.next.next:
            first = pre.next
            second = first.next
            remainder = second.next

            pre.next = second
            first.next = remainder
            second.next = first

            pre = first

        return dummy.next

The dummy node is not a replacement for any data node. It is a temporary predecessor that makes the head-changing case uniform.

The critical detail is this line:

remainder = second.next

It must happen before the rewiring. Once second.next changes, the original suffix is no longer available through second.

The condition also matters:

while pre.next and pre.next.next:

Checking only pre.next is insufficient. A final single node is not a complete pair, and evaluating pre.next.next without first confirming pre.next exists can raise an error.

Common mistakes:

• Returning head instead of dummy.next: the head changes whenever the list has at least two nodes.
• Swapping values: the visible sequence may look right, but node identity was not rearranged.
• Forgetting remainder: later nodes can become unreachable.
• Advancing pre to second: second is the new head of the pair, not its tail. The new tail is first.
• Using an unsafe loop condition: one-node and empty lists must stop cleanly.
• Creating new data nodes: this avoids the pointer problem instead of solving it and can violate the in-place contract.

A recursive formulation is also natural: recursively swap the suffix beginning at the third node, then connect the second node to the first. Its time complexity is still linear, but the call stack grows with the list. I prefer the iterative version here because the ownership changes are visible, the auxiliary space is constant, and the loop invariant maps directly to the code.

Complexity and edge-case audit

Each node participates in at most one pair transformation. The loop advances by two nodes, and each iteration performs a constant number of pointer reads and writes.

• Time: O(n), where n is the number of nodes.
• Auxiliary space: O(1) for the iterative solution.
• Node allocation: one temporary dummy node; no replacement data nodes are created.
• Recursion alternative: O(n) call-stack space because each pair adds a recursive call.

Before submitting, audit these cases:

Input shape	Expected behavior
Empty list	Return None
One node	Leave it unchanged
Exactly one pair	Return the second node as the new head
Odd length	Swap complete pairs; preserve the final node
Even length	Swap every node in a pair
Multiple pairs	Reconnect each transformed pair to the next
Repeated values	Use links and positions, not value comparisons

Repeated values are a useful test because they expose a weak implementation strategy. The algorithm must work because it tracks node positions, not because values happen to identify nodes.

Debugging check: After every pair swap, verify the three links as a chain: processed prefix → second → first → remainder. If one of those four regions disappears, the mutation order or pointer assignment is wrong.

The transferable pattern

Local linked-list transformations become easier when you stop treating pointers as vague arrows and start treating them as obligations.

Before assigning anything, name:

• the predecessor of the local region,
• the affected nodes,
• the untouched remainder.

Then preserve reachability, perform the rewiring, advance to the new local tail, and test the smallest boundary cases first.

For pair swapping, the compact rule is:

pre → first → second → remainder

becomes:

pre → second → first → remainder

Capture the remainder. Rewire the three links. Move the boundary forward.

That is the durable skill: local ownership handoff without losing the global chain.