Link to Question

MEDIUM

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

Input:

head = [1,2,3,4]

Output:

[2,1,4,3]

Explanation:
The list 1->2->3->4 is swapped to 2->1->4->3.

---

Constraints

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

---

Solution: Iterative

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

C++

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr)  return head;
        ListNode* dummy = new ListNode(0, head);
        ListNode* cur = dummy, *n = dummy->next;
        while(cur->next && n->next) {
            // Swap nodes
            cur->next = n->next;
            n->next = n->next->next;
            cur->next->next = n;

            // Move pointers for the next swap
            cur = cur->next->next;
            n = n->next;
        }
        return dummy->next;
    }
};