Hoán đổi nút theo cặp trong danh sách liên kết C++

Cho một danh sách liên kết. Yêu cầu hoán đổi mỗi hai nút liền kề và trả về nút đầu (head) của danh sách mới. Ràng buộc: không được sửa giá trị của các nút, chỉ được thay đổi liên kết giữa các nút. Ví dụ: danh sách [1,2,3,4] → kết quả [2,1,4,3].

Giải pháp:

• Nếu head rỗng → trả về head.
• first := head, second := head->next, dummy là nút mới giá trị -1.
• dummy->next := first, prev := dummy.
• While second != null:
  • temp := second->next.
  • first->next := second->next.
  • second->next := first.
  • prev->next := second.
  • prev := first.
  • Nếu temp != null: first := temp, second := temp->next; ngược lại break.
• Trả về dummy->next.

Ví dụ C++

#include <bits/stdc++.h>
using namespace std;

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

ListNode *make_list(vector<int> 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<int> v = {1,2,3,4,5,6,7,8};
    ListNode *head = make_list(v);
    print_list(ob.swapPairs(head));
}

Đầu vào

[1,2,3,4,5,6,7,8]

Đầu ra

[2,1,4,3,6,5,8,7]