Segmentation fault on XOR linked lists implementation

Question

The code's pretty simple and maybe I'm missing something obvious that's causing the segmentation fault. At a glance, the doubly XOR linked lists implementation code (intends to) create three nodes, and traverse them in a left to right fashion.

#include <iostream>

using namespace std;

typedef struct node { int data = 0; struct node* npx = NULL; }n;

n *zor(n *a, n *b) {
    return (n*)((uintptr_t) a ^ (uintptr_t) b);
}

int main() {

    n *head, *a, *b;

    head = new n;
    a = new n;
    b = new n;

    head->npx = zor(NULL, a);
    a->npx = zor(head, b);
    b->npx = zor(a, NULL);

    n* ptr = head;
    while (ptr != NULL) {
        cout << ptr->data;
        ptr = zor(ptr, ptr->npx);
    }
}

I expect the output to be "000" after traversing all the nodes in the list.

Answer 1

What went wrong

The links were built correctly combining the previous pointer with the next pointer.

link = previous ^ next

Unfortunately when the next pointer is recovered later

ptr = zor(ptr, ptr->npx);

tries to reconstruct next with

next = current ^ link

instead of

next = previous ^ link

resulting in a corrupted next. This means you need a bit more book keeping to keep track of that previous node.

Possible solution

n* current = head; // changed name to make code match description
n* previous = NULL; // no previous at the head
while (current != NULL) {
    cout << current->data;
    n* next = zor(previous, current->npx); // need a temp so we can update previous
    previous = current; // current becomes the next's previous
    current = next; // advance current to next
}