克隆带有下一个随机指针| Set 1的链表

您将获得一个双链接列表，每个节点的一个指针指向下一个节点，就像在单链接列表中一样。但是，不能将指针指向第二个节点，而只能指向第二个节点。现在写一个程序 O（n）时间 复制此列表。也就是说，编写一个程序来创建这个列表的副本。

让我们将第二个指针称为arbit指针，因为它可以指向链表中的任意节点。

图1

任意指针显示为红色，下一个指针显示为黑色

方法1（使用O（n）额外空间） 此方法首先将（原始列表的）下一个映射和任意映射存储在数组中，然后修改原始链表（创建副本），创建副本。最后恢复原始列表。

1） 使用下一个指针在复制链表中创建所有节点。 2） 存储原始链表的节点及其下一个指针映射。 3） 将原始链表中所有节点的下一个指针更改为指向复制链表中相应的节点。 下图显示了以上三个步骤后两个链表的状态。红色箭头显示arbit指针，黑色箭头显示下一个指针。

图2

4） 将复制链表中所有节点的arbit指针更改为指向原始链表中相应的节点。 5） 现在，在复制链表中构建arbit指针，如下所示，并恢复原始链表中节点的下一个指针。

       copy_list_node->arbit =                      copy_list_node->arbit->arbit->next;       copy_list_node = copy_list_node->next; 

6） 从存储的映射中恢复原始链表中的下一个指针（在步骤2中）。

时间复杂度：O（n） 辅助空间：O（n）

方法2（使用恒定的额外空间） 感谢Saravanan Mani提供此解决方案。这个解决方案使用常量空间。 1） 创建节点1的副本并将其插入原始链表中的节点1和节点2之间，创建节点2的副本并将其插入2和3之间。。以这种方式继续，在第N个节点后添加N的副本 2） 现在以这种方式复制任意链接

     original->next->arbitrary = original->arbitrary->next;  /*TRAVERSE TWO NODES*/

这是因为“原始->下一步”只不过是“原始->任意->下一步”只不过是“任意”的副本。 3） 现在，以这种方式在单个循环中恢复原始和复制链接列表。

     original->next = original->next->next;     copy->next = copy->next->next;

4） 确保original->next的最后一个元素为空。

有关此方法的实现，请参阅下面的帖子。 在O（1）空间中克隆带有下一个随机指针的链表

时间复杂度：O（n） 辅助空间：O（1）

有关基于哈希的实现，请参阅以下帖子。 克隆带有下一个随机指针| Set 2的链表

瓦伦·巴蒂亚问。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。