algorithm - 循环异或链表？

Question

我在阅读有关 XOR 链表的内容时，我想到了一个问题，即 是否有可能有一个循环 XOR 链表？ 在我看来，即使我们以某种方式构建了这样一个列表，给定列表的头节点是不可能遍历它的。例如 - 让链表包含 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 链接中检索所有信息。

其实这就是Wikipedia article无论如何说:

To start traversing the list in either direction from some point, you need the address of two consecutive items, not just one

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