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

Question

链接列表带有两个指针,第一个指向下一个节点,另一个指向随机指针.随机指针指向LinkedList的任何节点.编写一个完整的程序来创建链接列表(c,c ++,c#)的副本,而不更改原始列表和O(n).

在其中一次采访中我被问到这个问题,我无法找出解决方案.帮助将不胜感激.

Answer 1

在线性时间复制普通链表显然是微不足道的.使这个有趣的唯一部分是"随机"指针.大概是"随机"你的意思是它指向同一链表中另一个随机选择的节点.据推测,意图是链表的副本重新创建完全相同的结构 - 即,'下一个'指针创建线性列表,而其他指针指向相同的相对节点(例如,如果随机指针在原始列表的第一个节点中指向原始列表中的第五个节点,则重复列表中的随机指针也将指向重复列表的第五个节点.

在N ²时间执行此操作相当容易.首先复制列表,忽略随机指针.然后一次遍历原始列表中的一个节点,并为每个节点再次遍历列表,找到随机指针所引用的列表中的哪个节点(即,通过next指针遍历多少个节点以查找next指针保持与random当前节点的指针相同的地址.然后遍历重复列表并反转 - 找到第N ^个节点的地址,并将其放入当前节点的随机指针.

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

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

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

当我们完成这项工作后,我们将在锁定步骤中浏览旧列表和新列表.对于旧列表中的每个节点,我们查看该节点的随机指针中的地址.我们在哈希表中查找与该地址相关联的位置,然后在该位置的新列表中获取节点的地址,并将其放入新列表的当前节点的随机指针中.然后我们前进到旧列表和新列表中的下一个节点.

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

Answer 2

方法概述
我们不会尝试从单词go创建新的链表.首先复制原始链接列表中的项目,然后将列表拆分为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;
}

第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的顺序.

Answer 3

澄清编辑:

如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艺术技巧不符合它.

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

Answer 4

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