在O（n）时间内创建链接列表的副本
链接列表带有两个指针，第一个指向下一个节点，另一个指向随机指针。 随机指针指向LinkedList的任何节点。 编写一个完整的程序来创建链表（c，c ++，c＃）的副本，而无需更改原始列表和O（n）。
在其中一次采访中我被问到这个问题，我无法找到解决方案。 帮助将不胜感激。
在线性时间复制普通链表显然是微不足道的。 使这个有趣的唯一部分是“随机”指针。 大概是“随机”你的意思是它指向同一链表中另一个随机选择的节点。 据推测，意图是链表的副本重新创建完全相同的结构 – 即，’下一个’指针创建线性列表，而其他指针指向相同的相对节点（例如，如果随机指针在原始列表的第一个节点中指向原始列表中的第五个节点，然后重复列表中的随机指针也指向重复列表的第五个节点。
在N 2时间执行此操作相当容易。 首先正常复制列表，忽略随机指针。 然后一次遍历原始列表中的一个节点，并为每个节点再次遍历列表，找到随机指针所引用的列表中的哪个节点（即，您通过next指针遍历多少个节点以查找next指针保持与当前节点的random指针相同的地址。然后遍历重复列表并反转 – 找到第N 个节点的地址，并将其放入当前节点的随机指针。
这是O（N 2 ）的原因主要是对正确节点的线性搜索。 为了获得O（N），那些搜索需要以恒定的复杂度而不是线性复杂度来完成。
显而易见的方法是构建一个哈希表，将原始列表中每个节点的地址映射到列表中该节点的位置。 然后我们可以构建一个包含新列表中节点地址的数组。
有了这些，修复随机指针非常容易。 首先，我们通过next指针遍历原始列表，复制节点，并构建通过next指针连接的新列表，但只留下随机指针。 当我们这样做时，我们将每个节点的地址和位置插入到哈希表中，并将新列表中的每个节点的地址插入到我们的数组中。
当我们完成这项工作后，我们将在锁定步骤中浏览旧列表和新列表。 对于旧列表中的每个节点，我们查看该节点的随机指针中的地址。 我们在哈希表中查找与该地址相关联的位置，然后在该位置的新列表中获取节点的地址，并将其放入新列表的当前节点的随机指针中。 然后我们前进到旧列表和新列表中的下一个节点。
当我们完成后，我们扔掉/销毁哈希表和数组，因为我们的新列表现在复制了旧列表的结构，我们不再需要额外的数据了。
方法概述
我们不会尝试从单词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的顺序。
澄清编辑：
BowieOwens指出，只有“随机”指针是唯一的，以下情况才有效。
我只是为了一般的想法而离开答案，但请不要投票，因为它绝对是错误的 。
如果我没有完全弄错的话，你可以不使用任何额外的存储空间。
在复制旧列表时，将旧节点中的random指针存储在新节点的random指针中。
然后，将旧节点的random指针设置为指向新节点。
这将为您提供旧列表和新列表之间的“zig-zag”结构。
伪代码：
Node* old_node = ; 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艺术技巧不符合它。
这确实会更改原始列表，但会恢复到原始状态。
我猜这是否允许取决于面试。
如您所知，O（n）表示线性。 由于您需要线性数据结构的副本，因此您不会遇到问题，因为您只需要遍历原始列表的节点，并且对于每个被访问节点，您将为新列表创建新节点。 我认为这个问题没有很好地制定，因为你需要知道一些方面来完成这项工作：这是一个循环实施？ 什么是“下一个”节点？ 节点的下一个节点或列表的第一个节点？ 列表如何结束？
也许这个问题是一个技巧，来测试你如何回答奇怪的问题，因为它只是非常简单：
1）迭代到每个节点
2）为其他链表创建新节点，并复制值。
成本总是O（n）：因为你只需要迭代到整个链表一次！
或者，你对他的问题有所了解。