A print spool is a singly linked list of job nodes. Firmware wants every two adjacent jobs flipped — cover sheet then body becomes body then cover — so the printer pulls the payload first. An odd leftover job stays as it arrived. The intern swapped the job ids sitting in val. The order on the operator screen looked swapped. The job objects were not. A status widget that still held the old first node walked the same next it always had, now wearing a different number.

Swap nodes in pairs rewires every two adjacent nodes and leaves a leftover odd node alone. The linked list post owns dummy nodes and splice. Reverse Linked List owns the three-pointer rewire. This prompt is Reverse Nodes in k-Group with k fixed at 2. That writeup owns counting a full group and leaving a short tail. Here we only care about reversing one pair at a time.

The problem

Given the head of a singly linked list, swap every two adjacent nodes and return the (possibly new) head. If the length is odd, the last node stays. Reverse by rewiring next, not by swapping values.

1 → 2 → 3 → 4 → null       →  2 → 1 → 4 → 3 → null
1 → 2 → 3 → 4 → 5 → null   →  2 → 1 → 4 → 3 → 5 → null
1 → null                   →  1 → null
(empty)                    →  (empty)

A node is the usual two fields:

final class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

Note: In-place means the same node objects, new next links. Swapping val on each pair passes a value-order test. The node that sat first in a pair is still first, now wearing its neighbor’s number — so the returned head is still the old first object. Reverse Linked List named that identity trap when the intern built a second chain.

Swap the values on each pair

Walk two steps at a time. Exchange val with the neighbor. The leftover odd node is never visited as a pair. Correct on numbers. Wrong on identity. Head never moves.

ListNode swapPairsByValues(ListNode head) {
    ListNode p = head;
    while (p != null && p.next != null) {
        int tmp = p.val;
        p.val = p.next.val;
        p.next.val = tmp;
        p = p.next.next;
    }
    return head;
}

Every listener still holding a node thinks the successors never changed — because they are holding the same objects, with the same next links, only the painted numbers moved. You paid an identity bug for a question the original nodes already answer by rewiring next.

Dummy, reverse the pair, walk to its tail

A dummy in front of head gives every pair — including the first, which becomes the new head — a predecessor, so the pair that starts at the old head is not a special case. before starts on dummy. Each iteration:

  1. If before.next or before.next.next is null, fewer than two nodes remain. Stop. That is the odd leftover.
  2. Otherwise reverse that pair. before is the node before the run; the run length is 2. Same idea as Reverse Nodes in k-Group — do not re-derive a count-k probe here.
  3. After the reverse, the old first node of the pair is now its tail. Move before onto that tail so the next check starts at the following pair.

Walk 1 → 2 → 3 → 4 → 5:

dummy → 1 → 2 → 3 → 4 → 5 → null

pair (1, 2) exists
  reverse:  dummy → 2 → 1 → 3 → 4 → 5
  before moves to 1  (old pair head, now pair tail)

pair (3, 4) exists
  reverse:  dummy → 2 → 1 → 4 → 3 → 5
  before moves to 3

pair from 3.next: only 5 remains
  stop

return dummy.next   →  2 → 1 → 4 → 3 → 5

When the first pair includes the old head, dummy.next is the new head after the first reverse. Returning the original head would hand back the tail of that first swapped pair.

ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode before = dummy;
    while (before.next != null && before.next.next != null) {
        ListNode first = before.next;
        ListNode second = first.next;
        ListNode after = second.next;

        before.next = second;
        second.next = first;
        first.next = after;

        before = first;
    }
    return dummy.next;
}

The three assignments are a reverse of length two: before.next becomes second (the new pair head), second.next becomes first, first.next becomes after. Then before moves onto first — the old pair head, now the tail. Reverse Linked List is the same save-then-rewire on a longer run; here the run is hardcoded to a pair.

Time is O(n) — each node is visited a constant number of times. Space is O(1) besides the dummy and the handful of pointers.

After the reverse, before must become first — the old pair head, now the tail. Leave before on dummy and the next iteration reverses the same pair again. Move it onto second (the new pair head) and the next pair starts at first, mixing a node you already placed with the following pair. The while condition that demands two successors is the leftover rule: an odd last node is not a pair; do not invent a partner for it.

Empty list and a single node already have no pair. The loop never runs. You return dummy.next, which is head.

What interviewers usually poke next

  • This is k-group with k = 2. Name the dummy, the two-node existence check, and the tail you advance onto. Then point at Reverse Nodes in k-Group instead of writing a second algorithm.
  • Odd length. They will ask what happens to the last node. Name the while condition. The wrong answer is “swap it with null” or “leave it hanging off the old head.”
  • Recursive version. Reverse the first pair (or return head if fewer than two remain), recurse on first.next after the reverse, attach first to the recursive head. Mention the O(n / 2) stack bill.
  • Do it by swapping values. Correct for value-order tests, and you should say why in-place rewiring is the list they actually handed you.
  • k is not 2. Stop specializing. That is k-group. Do not keep unrolling pairs.

You are done with this problem when you can swap 1 → 2 → 3 → 4 → 5 without touching 5, and you can name why before becomes the old first node of the pair you just reversed.