Chương trình hoán đổi nút danh sách liên kết theo cặp bằng C++

Cho danh sách liên kết, hoán đổi mỗi hai nút liền kề (theo cặp) và trả về đầu danh sách mới. Không được sửa giá trị nút, chỉ được thay đổi con trỏ. Ví dụ: [1,2,3,4] → [2,1,4,3].

Quy trình giải quyết

1. Nếu head rỗng, trả về head.
2. Khởi tạo first = head, second = head.next, nút giả dummy(-1) trỏ đến first, prev = dummy.
3. Trong khi second không null:
   • temp = second.next.
   • Hoán đổi: first.next = second.next, second.next = first, prev.next = second.
   • Cập nhật prev = first.
   • Nếu temp tồn tại: first = temp, second = temp.next, ngược lại thoát.
4. Trả về dummy.next.

Ví dụ mã nguồn (C++)

#include 
using namespace std;

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int data) {
        val = data;
        next = NULL;
    }
};

ListNode* make_list(vector v) {
    ListNode *head = new ListNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        ListNode *ptr = head;
        while (ptr->next != NULL) ptr = ptr->next;
        ptr->next = new ListNode(v[i]);
    }
    return head;
}

void print_list(ListNode *head) {
    ListNode *ptr = head;
    cout << "[";
    while (ptr->next) {
        cout << ptr->val << ", ";
        ptr = ptr->next;
    }
    cout << "]" << endl;
}

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head) return head;
        ListNode* first = head;
        ListNode* second = head->next;
        ListNode* dummy = new ListNode(-1);
        dummy->next = first;
        ListNode* prev = dummy;
        while (second) {
            ListNode* temp = second->next;
            first->next = second->next;
            second->next = first;
            prev->next = second;
            prev = first;
            if (temp) {
                first = temp;
                second = temp->next;
            } else break;
        }
        return dummy->next;
    }
};

int main() {
    Solution ob;
    vector v = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    ListNode *head = make_list(v);
    print_list(ob.swapPairs(head));
    // Output: [2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13, ]
}

Đầu vào

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

Đầu ra

[2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13, ]