Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]

Output: [2,1,4,3]

Explanation:

Example 2:

Input: head = []

Output: []

Example 3:

Input: head = [1]

Output: [1]

Example 4:

Input: head = [1,2,3]

Output: [2,1,3]

Constraints:

The number of nodes in the list is in the range [0, 100].
0 <= Node.val <= 100

Approach: Iterative with a Dummy Node

Algorithm

Create a dummy node that points to the head, so the first swap can be handled uniformly
Walk a pointer prev over the list; while prev.next and prev.next.next both exist, swap the next two nodes
Let first = prev.next and second = prev.next.next; rewire first.next = second.next, second.next = first, prev.next = second
Advance prev to first so the next pair starts after the pair just swapped
Return dummy.next, the new head of the list

Time & Space Complexity

Time Complexity: O(n) - each node is visited once
Space Complexity: O(1) - only a few pointers are used, no recursion stack

Java Implementation

public class SwapNodesInPairs {

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

        while (prev.next != null && prev.next.next != null) {
            ListNode first = prev.next;
            ListNode second = prev.next.next;

            first.next = second.next;
            second.next = first;
            prev.next = second;

            prev = first;
        }

        return dummy.next;
    }

    // ListNode definition (given by LeetCode)
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    private static ListNode build(int... vals) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int v : vals) {
            cur.next = new ListNode(v);
            cur = cur.next;
        }
        return dummy.next;
    }

    private static String toString(ListNode head) {
        StringBuilder sb = new StringBuilder("[");
        while (head != null) {
            sb.append(head.val);
            if (head.next != null) {
                sb.append(", ");
            }
            head = head.next;
        }
        return sb.append("]").toString();
    }

    // Test method
    public static void main(String[] args) {
        System.out.println("Input: head = [1, 2, 3, 4]");
        System.out.println("Output: " + toString(swapPairs(build(1, 2, 3, 4)))); // Expected: [2, 1, 4, 3]

        System.out.println("Input: head = []");
        System.out.println("Output: " + toString(swapPairs(build()))); // Expected: []

        System.out.println("Input: head = [1]");
        System.out.println("Output: " + toString(swapPairs(build(1)))); // Expected: [1]

        System.out.println("Input: head = [1, 2, 3]");
        System.out.println("Output: " + toString(swapPairs(build(1, 2, 3)))); // Expected: [2, 1, 3]
    }
}

Example Walkthrough

For head = [1, 2, 3, 4]:

dummy -> 1 -> 2 -> 3 -> 4, prev = dummy
First pair: first = 1, second = 2. Rewire to 1.next = 3, 2.next = 1, dummy.next = 2. List: dummy -> 2 -> 1 -> 3 -> 4, prev = 1
Second pair: first = 3, second = 4. Rewire to 3.next = null, 4.next = 3, prev.next = 4. List: dummy -> 2 -> 1 -> 4 -> 3
prev.next == null, loop ends; return dummy.next = 2

Key Points

No Value Swapping: Only the next pointers are rewired, values stay untouched
Dummy Node: Removes the special case of swapping the first two nodes
Three-Node Rewiring: Each swap reassigns first.next, second.next, and prev.next
Odd Length: A trailing single node is left in place because the loop requires two nodes ahead
O(1) Space: The iterative version avoids the recursion used by an alternative recursive solution