使用next和random指针复制链接列表,列表中只显示读取权限

Question

我需要使用next和random指针复制链表.下一个指针通常指向链表中的下一个元素,随机指针可能指向任何其他节点甚至自身.如果我不允许随时修改给定列表,只能在列表中给出读取权限,如何做到这一点.

Answer 1

优雅的解决方案(线性时间,恒定空间):

创建节点1,2,3 ... n的副本并将它们插入1和2,2和3之间,依此类推,暂时忽略该random字段.所以列表中总共有2n个节点.

现在random,使用以下方法以下列方式设置新节点中的字段值:

original.next.random = original.random.next

这是有效的,因为LHS是random新创建的节点中的字段,RHS是指向任意节点副本的指针,正是我们想要的.

现在,在一次传递中恢复原始链接列表,并返回新列表.

original.next = original.next.next;
copy.next = copy.next.next; 

解决方案来自这里.

Answer 2

最简单的解决方案就是这样......

您遍历原始链接列表并创建另一个链接列表,其节点与原始列表中的节点相同,并带有正确的next指针,指向新列表的相应节点.你保持random现在的指针.

当您遍历列表时,您还将旧列表的节点地址/指针和新列表的节点地址/指针放在associative array(AKA映射,哈希表等)上,其中旧列表的节点地址/指针是key新的list的节点地址/指针是value.

然后遍历新列表,并用对应于等于指针的关联数组替换random每个节点中的指针.valuekeyrandom

哈希表可以用作关联数组,以实现与原始列表中的元素数量成比例的时间和内存成本.

该解决方案的时间和空间复杂度均为O(n).