在O(n)时间内创建链表的副本

Question

给定一个带有两个指针的链表，第一个指向下一个节点，另一个是随机指针，它指向LinkedList的任何节点。编写一个完整的程序来创建LinkedList的副本（c、c++、c#），不改变原始列表，并且时间复杂度为O(n)。

我在面试中被问到了这个问题，但我无法找到解决方案。期待您的帮助。

- palak mehta

---

第一个指针指向哪个节点？从我正在阅读的上下文中，“下一个节点”并没有太多意义。 - OmnipotentEntity

我有什么遗漏吗？为什么不直接使用指向下一个节点的指针遍历列表，并以此方式复制列表呢？ - Eric J.

我怀疑面试问题的目的是促使候选人向面试官提问，例如指针的用途 - 因为否则这个问题对于面试来说似乎太简单了（除非这是一次电话筛选面试）。 - Dai

我认为问题的关键在于如何处理随机指针。复制只有一个下一个节点指针的链表是很容易的，时间复杂度为n。我假设复制品也必须有自己的随机指针。这些指针是否可以独立随机化，或者它们必须与原始列表具有相同的映射，这将是向面试官提出的一个好问题。 - mawicks

在此问题中，“随机”指针表示它可以指向列表中的任何节点，而不仅仅是下一个节点。该问题是创建原始列表的精确副本，并将其随机指针设置为副本上的相应节点。可以通过使用哈希映射或字典等关联结构轻松解决该问题。当您需要迭代并要求在恒定空间内实现解决方案时，这将成为更大的挑战。 - Alan

Answer 1

在线性时间内复制一个普通的链表显然很简单。唯一让这个问题有意思的是“随机”指针。也许你真正想表达的是它指向同一链表中另一个随机选择的节点。大概意图是复制的链表要精确地重新创建相同的结构，也就是说，“next”指针创建一个线性列表，而其他指针引用相对的相同节点（例如，如果原始列表的第一个节点的随机指针指向原始列表的第五个节点，则重复列表中的随机指针也将指向重复列表的第五个节点）。

以 N² 时间完成上述操作相当容易。首先按照普通方式复制列表，忽略随机指针。然后逐个节点遍历原始列表，并且对于每个节点，再次遍历该列表，找到随机指针所指向的列表中的哪个节点（即通过“next”指针遍历多少个节点才能找到一个“next”指针保存了与当前节点的随机指针相同的地址）。然后遍历重复列表并进行反转，找到第 N^th 个节点的地址，并将其放入当前节点的随机指针中。

这样做 O(N²) 主要是因为那些查找正确节点的线性搜索。要获得 O(N)，这些搜索需要具有常数复杂度，而不是线性复杂度。

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

有了这些，修复随机指针就相当容易。首先，通过“next”指针遍历原始列表，复制节点，并通过“next”指针构建新的连接列表，但保留随机指针不变。在执行此操作时，我们将每个节点的地址和位置插入哈希表，并将新列表中每个节点的地址插入数组中。

完成这一步骤后，我们将同时遍历旧链表和新链表。对于旧链表中的每个节点，我们查看该节点的随机指针中存储的地址。我们在哈希表中查找与该地址相关联的位置，然后获取该位置上新链表中节点的地址，并将其放入新链表当前节点的随机指针中。接着，我们将遍历旧链表和新链表中的下一个节点。

完成以上操作后，我们可以丢弃/销毁哈希表和数组，因为新链表现在已经复制了旧链表的结构，我们不再需要额外的数据。

- Jerry Coffin

---

好的观点，如果没有进一步的注意，你不能只复制第一个节点，因为它指向一个尚不存在的节点。 - Eric J.

+1 对于理解当 OP 写道“给定一个带有两个指针的链接列表”时，所指的是“一个包含两个指针节点的链表”的内容。 - Jim Balter

完美的答案。这样你只需要遍历两次，而不是O(n^2)。+1 - Binayaka Chakraborty

Answer 2

方法概述
我们不会一开始就尝试创建一个新的链表。首先复制原始链表中的项目，然后将该列表分成两个相同的列表。

详细信息
步骤1：使用下一个指针遍历链表并创建每个节点的副本。

original :: A -> B -> C -> D -> E ->null

updated :: A -> A' -> B -> B' -> C -> C' -> D -> D' ->E -> E' -> null

这个可以在一个循环中轻松完成。

步骤2：再次遍历列表，并像这样修复随机指针。

Node *current= start;
Node *newListNode, *random;
while (current!= null) {
    // If current node has a random pointer say current = A, A.random = D;
    if ( (*current)->random != null ) {
        // newListNode will point to A'
        newListNode = (*current)->next;
        random = (*current)->random;
        random = (*random)->next;
        // Make A' point to D's next, which is D'
        (*newListNode)->random = random;
    }
    // Here A'.random = D'
    // Current goes to the next node in the original list => B , and not A'
    current= (*newListNode)->next;
}

第三步 :: 将列表拆分为两个列表。这里只需要修复下一个指针。

Original :: A -> A' -> B -> B' -> C -> C' -> D -> D' ->E -> E' -> null
New :: A -> B -> C -> D -> E ->null
       A' -> B' -> C' -> D' -> E' ->null

Node *start1 = head;
Node *start2 = (*head) ->next      // Please check the boundary conditions yourself,
                                   // I'm assuming that input was a valid list
Node *next, *traverse = start2;
while (traverse != null) {
    next = (*traverse)->next;
    if (next == null) {
        (*traverse)->next = null;
        break;
    }
    (*traverse)->next = (*next)->next;
    traverse = next;
}

这样，您就在O(n)的时间内创建了原始列表的副本。您需要遍历列表3次，但仍然是n的顺序。

- divyanshm

Answer 3

澄清编辑：

如BowieOwens指出的那样，下面的方法只有在“random”指针是唯一的情况下才有效。
我留下这个答案只是为了提供一般的思路，但请不要支持它，因为它绝对错误。

---

如果我没记错的话，您可以在不使用任何额外存储的情况下完成此操作。

当您复制旧列表时，在新节点的随机指针中存储旧节点的随机指针。
然后，将旧节点的随机指针设置为指向新节点。

这将为您提供旧列表和新列表之间的“锯齿”结构。

伪代码：

Node* old_node = <whatever>;
Node * new_node = new Node;
new_node->random = old_node->random;
old_node->random = new_node;

一旦你像这样复制了旧列表，你需要重新开始，但是需要替换random指针，同时将旧列表中的指针恢复到其原始状态，然后将新列表中的random指针设置为相应的新节点：

Node* old_random = old_node->random->random; // old list -> new list -> old list
Node* new_random = new_node->random->random; // new list -> old list -> new list
old_node->random = old_random;
new_node->random = new_random;

纸上看起来更好，但我担心我的ASCII艺术技能还不够好。

这确实改变了原始列表，但它被恢复到原始状态。
是否允许这样做取决于面试，我想。

- molbdnilo

---

当链表中的两个节点都指向同一个随机节点时，这是否会出现问题？ - Bowie Owens

+1：不确定这是否确切地回答了问题，但无论如何这是一种相当酷的技巧。 - Jerry Coffin

@BowieOwens：你的意思是我发布的图片里面有吗？我不认为有。 - molbdnilo

当更新第二对节点时，第一个旧节点的随机成员已经被恢复为其原始值（即它本身）。因此，new_node->random->random将指向旧列表而不是新列表，正如您所假设的那样。因此，第二个新节点和旧节点中的随机指针都将指向旧头节点。 - Bowie Owens

@BowieOwens：你说得完全正确。我有点感觉它太聪明了，而且确实是这样。 - molbdnilo

Answer 4

正如你所知，O(n) 意味着线性。如果你需要一个线性数据结构的副本，你不会遇到任何问题，因为你只需要迭代原始列表的节点，并为每个访问的节点创建一个新节点作为新列表。我认为这个问题表述不够清楚，因为你需要了解一些方面才能完成工作，例如：这是一个循环实现吗？"下一个"节点是什么？一个节点的下一个节点还是列表的第一个节点？列表如何结束？

- davidbuzatto

Answer 5

也许这个问题是一个考验，测试你如何回答奇怪的问题，因为它非常简单：

1）迭代到每个节点

2）为其他链接列表创建新节点，并复制值。

成本始终为O(n)：因为您只需一次迭代整个链接列表！！！

或者，您对他的问题有误解。

- hqt

---

每个节点都有一个随机指针。在一次遍历中，您无法创建完全相同的副本（重复列表中随机指针的值应与原始列表中的随机指针相同）。 - divyanshm

@DownVoter请解释一下为什么你要给我点踩。有什么问题吗？ - hqt

@hqt 可能是因为它假定数据只是数据，而实际上它是链表中某个项目的绝对引用，应该将其转换为链表新项目的绝对引用。 - wizzwizz4