c# - 在 O(n) 时间内创建链表的拷贝

Question

链表有两个指针，第一个指向下一个节点，另一个是随机指针。随机指针指向 LinkedList 的任何节点。编写一个完整的程序来创建链表的拷贝(c，c++，c#)，而不更改原始列表并且在 O(n) 中。

我在一次采访中被问到这个问题，但我想不出解决办法。帮助将不胜感激。

Answer 1

在线性时间内复制一个普通的链表显然是微不足道的。唯一使这变得有趣的部分是“随机”指针。据推测，“随机”实际上是指它指向同一链表中另一个随机选择的节点。据推测，其意图是链表的拷贝重新创建完全相同的结构——即，“下一个”指针创建一个线性列表，而其他指针指向相同的相关节点(例如，如果随机指针原链表的第一个节点指向原链表的第五个节点，那么复制链表中的随机指针也指向复制链表的第五个节点。

在 N² 时间内完成此操作相当容易。首先正常复制列表，忽略随机指针。然后一次遍历原始列表一个节点，对于每个节点再次遍历列表，以查找随机指针引用的列表中的哪个节点(即，您通过 next 指针遍历了多少个节点以找到一个 next 指针，它与当前节点的 random 指针保持相同的地址。然后遍历重复列表并反转它——找到第 N^th 节点的地址，并将其放入当前节点的随机指针。

这是 O(N²) 的原因主要是那些对正确节点的线性搜索。要获得 O(N)，这些搜索需要以恒定复杂度而不是线性复杂度来完成。

这样做的明显方法是构建一个哈希表，将原始列表中每个节点的地址映射到该节点在列表中的位置。然后我们可以构建一个数组来保存新列表中节点的地址。

有了这些，修复随机指针就很容易了。首先，我们通过next遍历原始列表。指针，复制节点，并构建我们通过 next 连接的新列表指针，但不理会随机指针。当我们这样做时，我们将每个节点的地址和位置插入到哈希表中，并将新列表中每个节点的地址插入到我们的数组中。

完成后，我们将同步检查旧列表和新列表。对于旧列表中的每个节点，我们查看该节点随机指针中的地址。我们在哈希表中查找与该地址关联的位置，然后在该位置获取新列表中节点的地址，并将其放入新列表当前节点的随机指针中。然后我们前进到旧列表和新列表中的下一个节点。

当我们完成后，我们丢弃/销毁哈希表和数组，因为我们的新列表现在复制了旧列表的结构，我们不再需要额外的数据。