Linked List

24. Swap Nodes in Pairs

In order to solve this problem, we need to keep the prev, a, and b information. After the swap, we will have

a -> next = b -> next;
b -> next = a;
prev -> next = b;
prev = a;
a = a -> next;

The code is shown here:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        auto dummy = new ListNode(-1);
        dummy -> next = head;
        auto prev = dummy;
        auto a = head;
        while (true) {
            if (a == nullptr) break;
            auto b = a->next;
            if (b == nullptr) break;
            a -> next = b -> next;
            b -> next = a;
            prev -> next = b;
            prev = a;
            a = a -> next;
        }
        return dummy -> next;
    }
};