Swap Nodes in Pairs

Share

Given a linked list, swap every two adjacent nodes and return its head. The values inside the nodes must not be modified: only node rearrangement is allowed.

Example 1
Input: head = [1,2,3,4]
Output: [2,1,4,3]
Explanation: Pairs (1,2) and (3,4) swapped.
Example 2
Input: head = [1]
Output: [1]

Solution Approach

Use a dummy head. For each pair: link dummy→second, second→first, first→next pair start. Advance dummy by 2.

  • dummy.next = second; second.next = first; first.next = next pair
  • Advance: dummy = first (now behind next pair)
Java
public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode curr = dummy;
    while (curr.next != null && curr.next.next != null) {
        ListNode first = curr.next, second = curr.next.next;
        first.next = second.next;
        second.next = first;
        curr.next = second;
        curr = first;
    }
    return dummy.next;
}
Complexity Analysis:

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