0024. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

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]

Constraints:

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

Follow up: Can you solve the problem without modifying the values in the list's nodes? (i.e., Only nodes themselves may be changed.)

Analysis

curent state: t -> a -> b -> c target state: t -> b -> a -> c

1. connect t with b
2. connect a with c
3. connect b with a
4. proceed forward t with two more steps

Time: $O(n)$

Space: $O(1)$

Code

class Solution {
public:
    ListNode* swapPairs(ListNode* head)
    {
        ListNode *dummy = new ListNode(-1), *t = dummy;
        dummy->next = head;
        while (t && t -> next && t -> next -> next) {
            auto *a = t -> next, *b = t -> next -> next, *c = t -> next -> next -> next;
            t -> next = b;
            a -> next = c;
            b -> next = a;
            t = t -> next -> next;
        }
        return dummy -> next;
    }
};

---

Last update: April 1, 2022