Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return the new head. Swap the nodes themselves, not only their values. With an odd number of nodes, the last one stays where it is.

LeetCode: 24. Swap Nodes in Pairs

Example

Text

Input:  1 -> 2 -> 3 -> 4 -> 5
Output: 2 -> 1 -> 4 -> 3 -> 5

Brute force: swap the values

Copy the values into a list, swap each pair there, and build a new list. This is straightforward, but it creates new nodes instead of moving the existing ones, which the problem doesn't allow.

A list node here is an object with a mutable next field, and null marks the end of the list.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

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

    static ListNode swapPairs(ListNode head) {
        List<Integer> values = new ArrayList<>();
        for (ListNode n = head; n != null; n = n.next) values.add(n.val);
        for (int i = 0; i + 1 < values.size(); i += 2) {
            Collections.swap(values, i, i + 1);
        }
        ListNode result = null;
        for (int i = values.size() - 1; i >= 0; i--) {
            result = new ListNode(values.get(i), result);
        }
        return result;
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        System.out.println(show(swapPairs(fromArray(1, 2, 3, 4, 5))));
    }
}

Output

[2, 1, 4, 3, 5]

Time: O(n). Space: O(n).

Optimal: relink in place

Put a dummy node in front of the head, so the first pair has a predecessor like every other pair. With cur pointing at the node before a pair first -> second -> rest:

Set first.next = second.next (that is rest).
Set second.next = first.
Set cur.next = second.
Move cur forward onto first, which is now the node before the next pair.

The loop continues while both cur.next and cur.next.next exist. If only one node is left, it stays in place.

graph LR
    subgraph before["before"]
        c1["cur"] --> f1["1 (first)"] --> s1["2 (second)"] --> r1["3 (rest)"]
    end
    subgraph after["after"]
        c2["cur"] --> s2["2"] --> f2["1 (next cur)"] --> r2["3"]
    end

Java

public class Main {
    static class ListNode {
        int val;
        ListNode next;

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

    static ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            ListNode first = cur.next;
            ListNode second = first.next;
            first.next = second.next; // 1. first points past the pair
            second.next = first;      // 2. second points back at first
            cur.next = second;        // 3. the previous node points at second
            cur = first;              // 4. first is now the node before the next pair
        }
        return dummy.next;
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        System.out.println(show(swapPairs(fromArray(1, 2, 3, 4, 5))));
        System.out.println(show(swapPairs(fromArray(1, 2, 3, 4))));
        System.out.println(show(swapPairs(fromArray(1))) + " " + show(swapPairs(null)));
    }
}

Output

[2, 1, 4, 3, 5]
[2, 1, 4, 3]
[1] []

Time: O(n). Space: O(1).

The order of the three assignments matters. Each one overwrites a next field whose old value is still needed by a later line, so first.next = second.next runs before second.next = first.

Edge cases

Empty list or single node: returned unchanged, because the loop condition fails at once.
Odd length: the last node stays, because cur.next.next is null and the loop ends.