深度复制带有随机指针的链表

“复制带随机指针的链表” 在这个问题中，我们需要实现的功能是对一个具有随机指针的链表进行深拷贝。链表的每个节点不仅有一个`next`指针，还有一个`random`指针，可以指向链表中的任意节点或者`null`。我们的任务是创建一个新的链表，新链表中的每个节点都对应原链表中的一个节点，且新链表的结构和随机指针关系与原链表完全一致。 首先，我们理解一下数据结构。链表的节点由两部分组成：`val`和`random_index`。`val`存储节点的值，`random_index`则表示随机指针指向的节点在链表中的索引（如果随机指针为空，则`random_index`为`null`）。 解决这个问题的一个常见方法是使用“影子节点”技术。创建一个新的链表，同时保持原链表和新链表相邻，即新链表的每个节点紧跟着原链表的对应节点。这样，我们可以在遍历原链表时，轻松地更新新链表节点的`random`指针，而无需回溯。 以下是详细的步骤： 1. 初始化一个空的新链表new_head，用于存放拷贝后的链表头节点。 2. 遍历原链表，对于每个节点node，我们在新链表中创建一个新节点new_node，将new_node的`val`设置为node的`val`。 3. 在新链表中，令new_node的`next`指针指向原链表下一个节点对应的新节点，即`new_node.next = node.next`。 4. 对于原链表的每个节点node，我们根据其`random_index`找到`random`指针指向的新节点new_random，然后设置`new_node.random = new_random`。 5. 完成遍历后，返回new_head，它就是深拷贝后的链表头节点。 需要注意的是，由于`random_index`是索引而非实际节点引用，我们需要在遍历过程中维护一个节点映射表，以便根据索引快速找到新链表中对应的新节点。这样，在处理`random`指针时，我们可以直接从映射表中获取新节点，而无需遍历整个新链表。 在处理边界条件时，例如空链表，我们需要确保在没有节点的情况下正确处理new_head。对于示例4，当输入为`head=[]`时，输出也应为`[]`，即空链表。 这个算法的时间复杂度是O(n)，因为我们需要遍历链表一次，创建新节点并设置指针。空间复杂度也是O(n)，因为我们需要存储新链表的所有节点以及节点映射表。 通过这种方法，我们可以成功地解决这个链表复制的问题，同时满足题目的所有要求。