แปลง Singly Linked List เป็น XOR Linked List ใน C++

ภาพรวมปัญหา

แปลง Singly Linked List เป็น XOR Linked List (เก็บ XOR ของ Address ก่อนหน้าและถัดไป)

ตัวอย่างโค้ด C++

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

struct Node {
    int data;
    struct Node* next;
};

Node* newNode(int data) {
    Node* temp = new Node;
    temp->data = data;
    temp->next = NULL;
    return temp;
}

void print(Node* head) {
    while (head) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

Node* XOR(Node* a, Node* b) {
    return (Node*)((uintptr_t)(a) ^ (uintptr_t)(b));
}

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;
    }
}

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 << "Before Conversion:\n";
    print(head);
    convert(head);
    cout << "After Conversion:\n";
    printXOR(head);
    return 0;
}

ผลลัพธ์ (Output)

Before Conversion:
1 2 3 4
After Conversion:
1 2 3 4