Swap Nodes in Pairs

medium linked list recursion

Problem

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed).

Inputhead = [1, 2, 3, 4]

Output[2, 1, 4, 3]

Use a dummy node so the new head can be returned uniformly. Three pointer rewrites per pair.

list (comma-separated)

def swap_pairs(head):
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next and prev.next.next:
        first = prev.next
        second = first.next
        first.next = second.next
        second.next = first
        prev.next = second
        prev = first
    return dummy.next

function swapPairs(head) {
  const dummy = { val: 0, next: head };
  let prev = dummy;
  while (prev.next && prev.next.next) {
    const first = prev.next;
    const second = first.next;
    first.next = second.next;
    second.next = first;
    prev.next = second;
    prev = first;
  }
  return dummy.next;
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        while (prev.next != null && prev.next.next != null) {
            ListNode first = prev.next;
            ListNode second = first.next;
            first.next = second.next;
            second.next = first;
            prev.next = second;
            prev = first;
        }
        return dummy.next;
    }
}

ListNode* swapPairs(ListNode* head) {
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
    while (prev->next && prev->next->next) {
        ListNode* first = prev->next;
        ListNode* second = first->next;
        first->next = second->next;
        second->next = first;
        prev->next = second;
        prev = first;
    }
    return dummy.next;
}

Explanation

We need to flip every adjacent pair of nodes, and the catch is we must move the actual nodes around (not just swap their values). The clean way is to rewire next pointers two nodes at a time.

A dummy node placed before the head saves us from special-casing the first swap, since after swapping the first pair the head changes. A pointer prev always sits just before the pair we're about to swap.

For each pair we name them first and second. The three rewires are: first.next = second.next (first now points past the pair), second.next = first (second jumps ahead of first), and prev.next = second (the node before the pair now leads with second). Then we move prev to first, which is the new tail of the swapped pair.

The loop condition prev.next and prev.next.next ensures we only swap when a full pair exists, so a lone last node is left untouched.

Example: 1→2→3→4. First pair (1,2) becomes 2→1, then pair (3,4) becomes 4→3, giving 2→1→4→3. We return dummy.next, the new head.

Time: O(n) Space: O(1)