Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Swap Nodes in Pairs

Problem (restated)

Given the head of a singly linked list, swap every two adjacent nodes by rewiring pointers (do not swap values) and return the new head. A leftover last node stays in place.

Intuition

Each swap needs the node before the pair so you can retarget it at the second node. A dummy head makes the first pair the same as every later pair. After swapping a, b, the next prev is a (now the tail of the pair).

Approaches

Dummy pair swap

Unverified

Time O(n)Space O(1)

Idea. dummy→head. While two nodes remain: a, b = prev.next, a.next; splice prev → b → a → b.next; then prev = a.

Walkthrough. 1→2→3→4. First pair: dummy→2→1→3→4. Then prev is 1; second pair: 1→4→3. Result 2→1→4→3.

Trade-offs. O(1) extra space. Draw the four pointers (prev, a, b, b.next) before writing; a missed assignment creates a cycle or drops a node.

Solution

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function swapPairs(head: ListNode | null): ListNode | null {
  const dummy = new ListNode(0, head);
  let prev = dummy;
  while (prev.next && prev.next.next) {
    const a = prev.next;
    const b = a.next!;
    a.next = b.next;
    b.next = a;
    prev.next = b;
    prev = a;
  }
  return dummy.next;
}

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function swapPairs(head: ListNode | null): ListNode | null {
  const dummy = new ListNode(0, head);
  let prev = dummy;
  while (prev.next && prev.next.next) {
    const a = prev.next;
    const b = a.next!;
    a.next = b.next;
    b.next = a;
    prev.next = b;
    prev = a;
  }
  return dummy.next;
}

Recursive pair swap

Unverified

Time O(n)Space O(n) stack

Idea. Base: fewer than two nodes. Let nxt be the second node; head.next = swapPairs(nxt.next), then nxt.next = head. Return nxt as the new pair head.

Walkthrough. Same list: innermost call leaves 3→4 swapped as 4→3, then 1↔2 with 1.next pointing at 4.

Trade-offs. Compact, but O(n/2) stack frames. Iterative is the interview default; recursion is a clean follow-up.

Solution

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function swapPairs(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head;
  const nxt = head.next;
  head.next = swapPairs(nxt.next);
  nxt.next = head;
  return nxt;
}

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function swapPairs(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head;
  const nxt = head.next;
  head.next = swapPairs(nxt.next);
  nxt.next = head;
  return nxt;
}

Template connection

Group-swap shape of Linked List Manipulation: dummy head plus a local reverse of length 2. LC 25 generalizes the same idea to k.

Reflection

A pair a -> b becomes b -> a. The dummy keeps the new head when the first pair swaps.
A leftover single node stays where it is. An empty list and a one-node list are themselves.
Cutting next before you save it drops the tail. Recursion swaps the same pairs.