Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Swap Nodes in Pairs

Swap Nodes in Pairs

Master this topic with zero to advance depth.

Swap Nodes in Pairs

Swap every two adjacent nodes.

Visual Representation

1 -> 2 -> 3 -> 4 Result: 2 -> 1 -> 4 -> 3
Medium

Examples

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

Level I: Recursive

Intuition

Swap first two nodes, recurse for the rest.

⏱ O(N)💾 O(N)
java
public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode next = head.next;
    head.next = swapPairs(next.next);
    next.next = head;
    return next;
}
Approach 2

Level III: Optimal (Iterative)

Intuition

Use a dummy node to simplify head swapping. Use a prev pointer to track the node before the current pair being swapped.

⏱ O(N)💾 O(1)

Detailed Dry Run

Dummy -> 1 -> 2 -> 3 -> 4. Prev = Dummy.

  1. First = 1, Second = 2.
  2. Prev.next = 2.
  3. 1.next = 3.
  4. 2.next = 1. Prev = 1.
java
public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0, head), prev = dummy;
    while (prev.next != null && prev.next.next != null) {
        ListNode first = prev.next, second = prev.next.next;
        first.next = second.next;
        second.next = first;
        prev.next = second;
        prev = first;
    }
    return dummy.next;
}
← Previous QuestionOdd Even Linked List
Next Question →Rotate List