1. Problem Link 🔗

LeetCode 24: Swap Nodes in Pairs

2. Solution Overview 🧭

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:

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

Input: head = []
Output: []

Input: head = [1]
Output: [1]

Constraints:

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

Common approaches include:

• Iterative with Dummy Node: Use a dummy node and swap pairs iteratively
• Recursive Approach: Recursively swap pairs and connect results
• Three Pointers: Use three pointers for swapping without dummy node

3. Solution 1: Iterative with Dummy Node (Recommended)

3.1. Algorithm

• Use a dummy node to handle edge cases (empty list, single node)
• Maintain pointers: prev, first, second
• For each pair: swap first and second, update connections
• Move pointers forward by two nodes

3.2. Important Points

• Most intuitive and commonly used approach
• Handles all edge cases gracefully
• Easy to understand and implement

3.3. Java Implementation

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        // Create dummy node to handle edge cases
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        while (prev.next != null && prev.next.next != null) {
            // Nodes to be swapped
            ListNode first = prev.next;
            ListNode second = prev.next.next;
            
            // Swap the pair
            first.next = second.next;
            second.next = first;
            prev.next = second;
            
            // Move prev two steps forward
            prev = first;
        }
        
        return dummy.next;
    }
}

3.4. Time & Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

4. Solution 2: Recursive Approach

4.1. Algorithm思路

• Recursively swap pairs from the end of the list
• Base case: empty list or single node
• For each pair: swap first two nodes, recursively process the rest
• Connect the swapped pair with the recursively processed list

4.2. Important Points

• Elegant and concise
• Uses O(n) stack space
• Good for understanding recursive thinking

4.3. Java Implementation

class Solution {
    public ListNode swapPairs(ListNode head) {
        // Base case: empty list or single node
        if (head == null || head.next == null) {
            return head;
        }
        
        // Nodes to be swapped
        ListNode first = head;
        ListNode second = head.next;
        
        // Swap and recursively process the rest
        first.next = swapPairs(second.next);
        second.next = first;
        
        // New head after swapping
        return second;
    }
}

4.4. Time & Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(n) for recursion stack

4. Solution Comparison 📊

Solution	Time Complexity	Space Complexity	Advantages	Disadvantages
Iterative with Dummy	O(n)	O(1)	Simple, handles edges well	Uses one extra node
Recursive	O(n)	O(n)	Elegant, concise	Stack overflow risk

6. Summary 📝

• Key Insight: Swap nodes in pairs by carefully updating the next pointers
• Recommended Approach: Solution 1 (Iterative with Dummy Node) is most commonly used
• Critical Technique: Using a dummy node simplifies edge case handling
• Pattern Recognition: This is a fundamental linked list manipulation pattern

Why Dummy Node Helps:

• Eliminates special handling for head swap
• Provides a consistent starting point
• Makes the algorithm more readable

The iterative approach with dummy node is generally preferred for its simplicity, efficiency, and robustness in handling all edge cases.