LeetCode. 24. Swap Nodes in Pairs

[Link] https://leetcode.com/problems/swap-nodes-in-pairs/

Swap each adjacent pair by relinking its next references; the values are never changed, and every input node is reused.

A dummy head gives the first pair a predecessor, so every pair follows the same steps. before marks the end of the prefix already placed in its final order. In each iteration, relink before -> first -> second -> rest as before -> second -> first -> rest, then advance before to first. This invariant keeps the processed prefix settled while preserving the unprocessed suffix.

The loop runs only when two nodes remain. If the list has an odd length, its final unpaired node stays in place. The dummy is the only temporary node; the returned list contains the original nodes. The algorithm takes $O(N)$ time and $O(1)$ extra space.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        // The dummy gives the first pair a predecessor just like every later pair.
        ListNode dummy = new ListNode(0, head);
        ListNode before = dummy;

        // Invariant: nodes before `before` are already in their final order.
        while (before.next != null && before.next.next != null) {
            ListNode first = before.next;
            ListNode second = first.next;

            // Relink the pair, preserving the remaining suffix.
            first.next = second.next;
            second.next = first;
            before.next = second;

            // Continue with the next pair after the two swapped nodes.
            before = first;
        }

        // A final unpaired node stays in place; no new list nodes are returned.
        return dummy.next;
    }
}