Node Swap

Tags

Node Swap

Category

Linked Lists

Difficulty

Hard

Problem Statement

Given a singly linked list, swap every two adjacent nodes and return the modified list's head. The swap must be performed by actually rearranging the nodes (not just swapping values). For example, given 1 -> 2 -> 3 -> 4, the result should be 2 -> 1 -> 4 -> 3.

Intuition

For each pair of adjacent nodes, we need to reverse their order while maintaining connections to the rest of the list. The tricky part is managing the pointer from the node before the pair to the new first node of the pair. Using a dummy/sentinel node before the head simplifies the logic by eliminating the special case for the first pair.

Approach

  1. Create a dummy node whose next points to the head of the list.
  2. Initialize a pointer prev at the dummy node.
  3. While there are at least two nodes ahead of prev: a. Let first = prev.next and second = prev.next.next. b. Rewire: first.next = second.next (first now points past second). c. Rewire: second.next = first (second now points to first). d. Rewire: prev.next = second (prev now points to second, which is the new first in the pair). e. Advance prev to first (which is now the second node in the swapped pair).
  4. Return dummy.next as the new head.

Pseudocode

function nodeSwap(head):
    dummy = new Node(0)
    dummy.next = head
    prev = dummy

    while prev.next is not null and prev.next.next is not null:
        first = prev.next
        second = prev.next.next

        // Perform the swap
        first.next = second.next
        second.next = first
        prev.next = second

        // Advance
        prev = first

    return dummy.next

Recursive alternative:

function nodeSwap(head):
    if head is null or head.next is null:
        return head

    first = head
    second = head.next

    first.next = nodeSwap(second.next)
    second.next = first

    return second

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. Each node is visited exactly once.
  • Space: O(1) for the iterative approach (only a few pointers). O(n/2) = O(n) for the recursive approach due to the call stack.

Key Insights

  • The dummy node pattern eliminates special-case handling for the head of the list, since the head changes after swapping the first pair.
  • The order of pointer reassignment matters: changing pointers in the wrong order can create cycles or lose references.
  • The iterative approach is preferred for O(1) space, but the recursive approach is more elegant and easier to understand.
  • After swapping a pair, prev advances to first (not second) because first is now the second node in the pair and thus the predecessor of the next pair.
  • This problem is a specific case of "reverse nodes in k-group" with k = 2.

Edge Cases

  • Empty list — return null.
  • Single node — no pair to swap; return the node unchanged.
  • Odd number of nodes — the last node has no pair and remains in place (e.g., 1 -> 2 -> 3 becomes 2 -> 1 -> 3).
  • Two nodes — a single swap occurs.
  • All nodes have the same value — swapping still happens (structural change), though the values look the same.
  • Very long list — the iterative approach handles it without stack overflow risk.

Linked mentions