Chuyển Danh Sách Liên Kết Đơn Thành Danh Sách XOR Trong C++

Trong hướng dẫn này, chúng ta sẽ thảo luận chương trình chuyển danh sách liên kết đơn (singly linked list) thành danh sách XOR linked list.

Cho một danh sách liên kết đơn. Nhiệm vụ là lấy các phần tử của danh sách đó và chuyển đổi thành danh sách XOR linked list.

Ví Dụ

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

// Cấu trúc nút danh sách liên kết
struct Node {
    int data;
    struct Node* next;
};

// Tạo nút mới
Node* newNode(int data) {
    Node* temp = new Node;
    temp->data = data;
    temp->next = NULL;
    return temp;
}

// In danh sách liên kết đơn
void print(Node* head) {
    while (head) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

// Tính giá trị XOR
Node* XOR(Node* a, Node* b) {
    return (Node*)((uintptr_t)(a) ^ (uintptr_t)(b));
}

// Chuyển danh sách liên kết đơn sang XOR
void convert(Node* head) {
    Node* curr = head;
    Node* prev = NULL;
    Node* next = curr->next;
    while (curr) {
        next = curr->next;
        curr->next = XOR(prev, next);
        prev = curr;
        curr = next;
    }
}

// In danh sách XOR
void printXOR(Node* head) {
    Node* curr = head;
    Node* prev = NULL;
    while (curr) {
        cout << curr->data << " ";
        Node* temp = curr;
        curr = XOR(prev, curr->next);
        prev = temp;
    }
    cout << endl;
}

int main() {
    Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    cout << "Trước khi chuyển đổi: " << endl;
    print(head);
    convert(head);
    cout << "Sau khi chuyển đổi: " << endl;
    printXOR(head);
    return 0;
}

Đầu Ra

Trước khi chuyển đổi: 1 2 3 4
Sau khi chuyển đổi: 1 2 3 4