Swap Nodes in Pairs

Swap every two adjacent nodes by moving pointers, not values. A dummy head gives every pair a node in front of it, even the first pair.

Time O(n)Space O(1)Code C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

A pair swap touches three links: the one into the pair, the one inside it, and the one out of it. prev is the node in front of the pair, so it can fix the link into the pair. Point first at whatever follows the pair, turn second round to point at first, then point prev at second. first ends up at the back of the pair, so it becomes prev for the next pair.

Code

public ListNode SwapPairs(ListNode head) {
    var dummy = new ListNode(0, head);
    ListNode prev = dummy;
    while (prev.next != null && prev.next.next != null) {
        ListNode first = prev.next, second = first.next;
        first.next = second.next; // first will be the back: it links to the rest
        second.next = first;      // second turns round to face first
        prev.next = second;       // the node before the pair now leads to second
        prev = first;             // first is now the back of the pair
    }
    return dummy.next;
}

Tips

The dummy node D is the node in front of the first pair, so swapping the head pair needs no special case and dummy.next is always the new head.
Do first.next = second.next before second.next = first, or the rest of the list is lost.
With an odd number of nodes the last one has no partner: the loop stops because prev.next.next is null, and it stays put.

In the .NET library

The problem asks you to move nodes, not values. Swapping val fields would pass simple tests but fails when nodes carry more data or other code holds references to them.