循环异或链表？

Question

我正在阅读 XOR 链表，我想到了一个问题，在我Is it possible to have a circular XOR linked list?看来，即使我们以某种方式构建了这样一个列表，也不可能在给定列表头节点的情况下遍历它。例如 - 让链表包含 3 个节点：A、B 和 C。

|
v
A ---> B ---> C

A->xor = B ^ C
B->xor = A ^ C
C->xor = A ^ B

由于我们已经给出head了列表，即A在这种情况下，我们将无法向前或向后移动，因为我们必须至少知道B或C中的一个才能移动。由于我们无法遍历它，因此我们也无法构建它。

我的想法正确吗？或者我错过了什么？

Answer 1

确实你是对的，因为我们无法从xor链接中检索任何指针值，所以不可能遍历这个列表。

这个列表变得可遍历的最低要求是两条信息……例如指向当前节点的指针和指向下一个（或上一个）节点的指针。然后您可以从xor链接中检索所有信息。

事实上，无论如何，这就是维基百科文章所说的：

要从某个点开始向任一方向遍历列表，您需要两个连续项目的地址，而不仅仅是一个

这仍然比为每个节点存储两个指针便宜，因为我们每个节点只需要一个链接，加上当前和下一个（或上一个）节点的两个指针。