6

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

我在一次采访中被问到这个问题，我无法弄清楚解决方案。帮助将不胜感激。

4

5 回答 5

17

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

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

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

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

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

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

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

于 2012-07-16T03:39:37.193 回答
8

方法概述
我们不会尝试从 go 一词开始创建新的链表。首先复制原始链表中的项目，然后将链表拆分为 2 个相同的链表。

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

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;
}

第 3 步:: 将列表拆分为 2 个列表。您只需要在此处修复下一个指针。

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 的顺序。

于 2013-05-04T06:42:20.500 回答
7

澄清编辑：

正如 BowieOwens 指出的那样，以下仅在“随机”指针是唯一的情况下才有效。
我只是为了一般的想法而留下答案，但请不要投票，因为它绝对是错误的。

如果我没有完全弄错，您可以在不使用任何额外存储空间的情况下执行此操作。

在复制旧列表时，将random旧节点的random指针存储在新节点的指针中。
然后，设置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 艺术技能达不到它。

这确实会更改原始列表，但会恢复到原始状态。
我猜这是否允许取决于面试。

于 2012-07-16T12:37:27.500 回答
0

如您所知，O(n) 表示线性。由于您需要线性数据结构的副本，因此您不会遇到问题，因为您只需要遍历原始列表的节点，并且对于每个访问的节点，您将为新列表创建一个新节点。我认为这个问题没有很好地表述，因为您需要了解一些方面才能完成这项工作：这是循环实现吗？“下一个”节点是什么？节点的下一个节点还是列表的第一个节点？清单如何结束？

于 2012-07-16T02:56:19.357 回答
-1

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

1）迭代到每个节点

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

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

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

于 2012-07-16T03:16:41.363 回答