The O(n) Club: Swap Nodes in Pairs — No, You Can’t Just Swap Values

The O(n) Club: Swap Nodes in Pairs — No, You Can’t Just Swap Values

⚡ TL;DR

Take a singly linked list and actually swap every pair of adjacent nodes—don’t even think about just swapping values. That’s not allowed, and your interviewer will see right through you. Here’s the O(n) pointer-juggling version in Java:

// Instant Java: swap node pairs (not values)
ListNode dummy = new ListNode(0, head);
ListNode curr = dummy;
while (curr.next != null && curr.next.next != null) {
  ListNode first = curr.next, second = curr.next.next;
  first.next = second.next;
  second.next = first;
  curr.next = second;
  curr = first;
}
return dummy.next;

🧠 How Devs Usually Mess This Up

If you immediately reached for temp values and swapped numbers instead of nodes—gently put, you missed the point. Read the instructions: node re-linking only.

Another classic move? Tripping over edge cases: what if the list is empty, only one node, or has an odd count? Suddenly you’re debugging pointer sorcery while your coffee goes cold. Last but not least: break the chain in the wrong place and you might create a cycle or send nodes into the void—at least garbage collection enjoys the company.

🔍 What’s Actually Going On

Imagine a row of people in a conga line. It’s pair swap time! But you can’t swap names—only actual places in line. You add a dummy node (think of it as a VIP velvet rope holder at the club’s entrance) to safely coordinate the first swap and always know where the head is, no matter how much the front changes.

Grab two at a time, quickly rearrange their hands (pointers), and march further. The process ripples down the chain in O(n) time, one hop at a time—no duplicating, no value shuffling, just some elegant pointer dancing.

🛠️ PseudoCode

• Add dummy node before head.
  This lets you swap the front pair with zero drama.
• Use a pointer curr at dummy.
  It’s your dance MC, handling the next swap.
• While there are at least 2 nodes to swap:

  // Pick dancers
  ListNode first = curr.next;
  ListNode second = curr.next.next;
  // Swap them
  first.next = second.next;
  second.next = first;
  curr.next = second;
  // Move MC to next pair
  curr = first;
  

• Return dummy.next—the new list head.

💻 The Code

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
    ListNode(int x, ListNode nxt) { val = x; next = nxt; }
}
 public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0, head);
    ListNode curr = dummy;
    while (curr.next != null && curr.next.next != null) {
        ListNode first = curr.next;
        ListNode second = curr.next.next;
        first.next = second.next;
        second.next = first;
        curr.next = second;
        curr = first;
    }
    return dummy.next;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Strictly swap nodes, never values. (Interviewers are watching.)
• Odd list? Solo node at end. That’s fine—let it be awkward at the dance.
• Edge cases galore: Empty, one element, just a pair—handle ’em or the bugs will handle you.
• Pointer links or cycles? One misstep, infinite loop or vanishing nodes. Keep pointer moves in order.
• Time & space? O(n) time, O(1) space. If you make a new list or stack up recursion, you’ve missed the club’s memo.

🧠 Interviewer Brain-Tattoo

“If you can’t swap adjacent nodes without a value crutch, maybe let the robots do the whiteboarding.”