C++ Hoán vị cặp phần tử trong danh sách liên kết

Hoán vị từng cặp nút liền kề trong danh sách liên kết. Ví dụ:

Input: 1→2→3→4→5→6 → Output: 2→1→4→3→6→5
Input: 1→2→3→4→5 → Output: 2→1→4→3→5
Input: 1 → Output: 1

Phương pháp lặp

Duyệt danh sách, hoán đổi data của cặp nút hiện tại và nút tiếp theo, nhảy 2 bước.

Ví dụ

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

class Node {
public:
    int data;
    Node* next;
};

void swapPairwise(Node* head) {
    Node* temp = head;
    while (temp && temp->next) {
        swap(temp->data, temp->next->data);
        temp = temp->next->next;
    }
}

void push(Node** head_ref, int data) {
    Node* new_node = new Node();
    new_node->data = data;
    new_node->next = *head_ref;
    *head_ref = new_node;
}

void printList(Node* node) {
    while (node) { cout << node->data << " "; node = node->next; }
}

int main() {
    Node* head = NULL;
    push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1);
    cout << "Trước: "; printList(head);
    swapPairwise(head);
    cout << "\nSau: "; printList(head);
    return 0;
}

Kết quả

Trước: 1 2 3 4 5
Sau: 2 1 4 3 5

Phương pháp đệ quy

Cùng logic, thay vòng lặp bằng gọi đệ quy cho cặp tiếp theo.

Ví dụ

void swapPairwise(Node* head) {
    if (head && head->next) {
        swap(head->data, head->next->data);
        swapPairwise(head->next->next);
    }
}

Kết luận

Đã trình bày 2 cách hoán vị cặp nút trong danh sách liên kết: lặp và đệ quy, đều O(N). Code C++ áp dụng cho các ngôn ngữ khác. Hy vọng hữu ích.