一个异或链表是一个正常双链表的修改版本,其中每个节点存储仅仅一个"指针",而不是两个.该"指针"由下一个和前一个指针的XOR组成.要遍历列表,需要两个指针 - 一个指向当前节点,另一个指向下一个或上一个节点.为了遍历前进,前一个节点的地址与存储在当前节点中的"指针"进行异或,显示真正的"下一个"指针.
C++标准导致指针和整数上的一系列操作导致未定义的行为 - 例如,您无法保证在数字中设置特定位不会导致硬件触发中断,因此在某些情况下会导致位的结果twiddling可以是undefined.
我的问题如下:是否有一个XOR链表的C++实现,不会导致未定义的行为？
如何只用一个指针实现双链表？
找到prev和next节点需要O(1)时间.
struct Node
{
int val;
Node* p;
};