LeetCode 24: Swap Nodes in Pairs

 Swap Nodes in Pairs - LeetCode Solution (C++)

Swapping adjacent nodes in a linked list is a common problem in coding interviews. We will explore different approaches, focusing on the optimal one.

---

Problem Statement

LeetCode 24: 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]

Example 2:

Input:

head = []

Output:

[]

Example 3:

Input:

head = [1]

Output:

[1]

---

Optimal Approach - Iterative Pointer Manipulation

Key Idea

1. Use a dummy node to simplify edge cases.
2. Maintain pointers to swap adjacent nodes.
3. Adjust pointers iteratively to swap pairs.

Time Complexity:

• O(N) where N is the number of nodes.

Space Complexity:

• O(1) as no extra space is used.

---

C++ Solution (LeetCode Compatible)

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(-1);
        dummy.next = head;
        ListNode* prev = &dummy;
        
        while (head && head->next) {
            ListNode* first = head;
            ListNode* second = head->next;
            
            prev->next = second;
            first->next = second->next;
            second->next = first;
            
            prev = first;
            head = first->next;
        }
        
        return dummy.next;
    }
};

---

Step-by-Step Code Explanation

1. Use a dummy node to handle edge cases.
2. Initialize prev pointer to the dummy node.
3. Traverse the list in pairs:
   • Assign first and second to the adjacent nodes.
   • Swap their connections.
   • Move prev and head to the next pair.
4. Return the modified list starting from dummy.next.

---

Dry Run / Execution Steps

Input:

head = [1,2,3,4]

Pointer Updates & Swaps

Step	Nodes Being Swapped	Modified List
1	1 ↔ 2	2 → 1 → 3 → 4
2	3 ↔ 4	2 → 1 → 4 → 3

Final Output:

[2,1,4,3]

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Notes
Brute Force (Recursion)	O(N)	O(N) (stack space)	❌ Not optimal for large lists
Iterative Swap (Best Approach) ✅	O(N)	O(1)	✅ Efficient pointer manipulation

Why Iterative Approach is Best?

✔ Constant space complexity.
✔ Handles edge cases smoothly.
✔ Efficient pointer adjustments.

---

Conclusion

• Best approach: Iterative Pointer Manipulation
• Why? Efficiently swaps adjacent nodes in O(N) time with O(1) space.
• Alternative: Recursive approach, but it consumes extra stack space.
• Practice More:
  • Reverse Linked List
  • Reverse Nodes in k-Group

Would you like more detailed tutorials like this? Let me know! 🚀