#24

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Swap Nodes in Pairs

Learn how to swap every adjacent linked-list pair by rewiring nodes safely without changing values or breaking the remaining chain.

linked list recursion

Problem Statement

You are given the head of a singly linked list and need to swap each adjacent pair of nodes, then return the new head. The swap must happen by changing links between nodes, not by overwriting node values. For example, when the input is [1,2,3,4], the correct result is [2,1,4,3] because nodes 1 and 2 switch places, then nodes 3 and 4 switch places.

This problem includes small edge cases that decide whether your pointer logic is correct. An empty list should stay empty, and a single-node list should remain unchanged because there is no pair to swap. The list length is at most 100, so the interview focus is not scaling tricks but whether you can rewire pairs cleanly without dropping nodes or creating bad links.

Examples

Example 1

Input: head = [1,2,3,4]

Output: [2,1,4,3]

Example 2

Input: head = []

Output: []

Example details omitted.

Example 3

Input: head = [1]

Output: [1]

Example details omitted.

Constraints

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

Solution Approach

Use a dummy node to simplify head swaps

The iterative pattern starts with a dummy node pointing to head so the first pair uses the same logic as every later pair. Track a previous pointer before the current pair, then identify first, second, and the node after the pair. Rewire in this order: previous points to second, first points to the node after the pair, and second points to first. Move previous to first and continue. This avoids special casing the original head after the first swap.

Preserve the next segment before changing links

The critical step in Swap Nodes in Pairs is saving access to the rest of the list before you flip any arrows. If first is the current node and second is first.next, store second.next before rewiring. Without that saved pointer, the remaining chain can become unreachable. This problem is less about cleverness and more about disciplined pointer order on every pair.

Recognize recursion as the same pair-swap pattern

The recursive version treats the first two nodes as one unit: swap them, then connect the original first node to the result of recursively solving the rest of the list. It is elegant because the pair boundary is explicit, but it uses call stack space. In interviews, recursion is acceptable here if you clearly explain the base case of zero or one node and show how the swapped front reconnects to the recursively processed tail.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

An iterative solution runs in O(n) time because each node is visited once as part of at most one pair swap, and it uses O(1) extra space aside from a few pointers. A recursive solution also runs in O(n) time, but its extra space is O(n) in the worst case because each pair contributes another call frame. For LeetCode 24, the real trade-off is not runtime but whether you want constant-space pointer control or shorter recursive code.

What Interviewers Usually Probe

They want to see whether you can swap the head pair without writing a fragile special case, which usually points to using a dummy node.
They are checking if you understand pointer-update order, especially saving the node after the current pair before rewiring.
If they mention recursion, they want you to compare cleaner expression against call-stack cost for this exact pair-swapping list problem.

Common Pitfalls or Variants

Common pitfalls

Updating first.next or second.next before saving the rest of the list, which disconnects the remaining nodes.
Moving the traversal pointer to the wrong node after a swap, causing skipped pairs or infinite loops.
Swapping node values instead of node links, which violates the problem requirement even if the output values look correct.

Follow-up variants

Swap nodes in groups of k, where this problem becomes the k = 2 version of linked-list group reversal.
Swap pairs recursively, then rewrite the same logic iteratively to remove stack usage.
Handle a doubly linked list version where both next and prev links must stay consistent after each pair swap.

FAQ

What is the main pattern in Swap Nodes in Pairs?

The core pattern is linked-list pointer manipulation on fixed-size groups of two. You repeatedly identify a pair, save the node after it, swap the two nodes by changing next pointers, and reconnect the swapped pair to the previous part of the list.

Why is a dummy node useful for LeetCode 24?

The first swap changes the head, so a dummy node removes that special case. It lets every pair use the same reconnection logic because the node before the pair always exists, even for the original head.

Can I solve Swap Nodes in Pairs with recursion?

Yes. Recursion works well because you swap the first two nodes, then attach the original first node to the recursively swapped remainder. The trade-off is extra call stack space compared with the iterative constant-space approach.

Why is swapping values not allowed here?

The problem explicitly requires swapping nodes themselves, not modifying stored values. That restriction tests whether you can manipulate linked-list structure rather than just reproduce the final sequence of numbers.

What usually breaks an otherwise correct pair-swap solution?

Most bugs come from pointer order. If you do not save the third node before rewiring the first two, or if you advance to the wrong node after a swap, the list can be truncated, misordered, or loop forever.

terminal

Solution

Solution 1: Recursion

We can implement swapping two nodes in the linked list through recursion.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        t = self.swapPairs(head.next.next)
        p = head.next
        p.next = head
        head.next = t
        return p

Solution 2: Iteration

We set a dummy head node $dummy$, initially pointing to $head$, and then set two pointers $pre$ and $cur$, initially $pre$ points to $dummy$, and $cur$ points to $head$.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        t = self.swapPairs(head.next.next)
        p = head.next
        p.next = head
        head.next = t
        return p

Continue Practicing

#25 reverse nodes in k group #21 merge two sorted lists #2 add two numbers