我在阅读有关 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
中的至少一个才能移动。由于我们无法遍历它,因此我们也无法构建它。
我的想法是否正确?还是我遗漏了什么?
最佳答案
确实你是对的,遍历这个列表是不可能的,因为我们无法从 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
这仍然比为每个节点存储两个指针要便宜,因为我们只需要每个节点一个链接,再加上当前和下一个(或上一个)节点的两个指针。
关于algorithm - 循环异或链表?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10995212/