DEV Community
·
Leetcode 138. 带随机指针的链表复制
💡
原文英文，约800词，阅读约需3分钟。
📝
内容提要
给定一个包含随机指针的链表，要求构建其深拷贝。新节点的值与原节点相同，且新节点的指针指向新链表中的节点。可以使用哈希表或在原链表中插入新节点的方法实现，时间复杂度为O(n)，空间复杂度分别为O(n)和O(1)。
🎯
关键要点
- 给定一个包含随机指针的链表，要求构建其深拷贝。
- 新节点的值与原节点相同，且新节点的指针指向新链表中的节点。
- 可以使用哈希表或在原链表中插入新节点的方法实现。
- 时间复杂度为O(n)，空间复杂度分别为O(n)和O(1)。
- 链表的每个节点包含一个额外的随机指针，可能指向链表中的任何节点或null。
- 深拷贝的链表应由n个全新节点组成，且新节点的next和random指针应指向新链表中的节点。
- 示例输入和输出展示了如何表示链表及其随机指针。
- 方法一：使用哈希表，遍历链表创建重复节点并存储在哈希表中。
- 方法二：在原链表中插入重复节点，随后映射随机指针。
- 最终步骤是标记下一个节点并提取最终结果。
❓
延伸问答
如何构建带随机指针的链表的深拷贝？
可以使用哈希表或在原链表中插入新节点的方法来构建深拷贝。
深拷贝的链表中，新节点的指针如何设置？
新节点的指针应指向新链表中的节点，确保与原链表的指针状态一致。
使用哈希表实现深拷贝的时间和空间复杂度是多少？
时间复杂度为O(n)，空间复杂度为O(n)。
在原链表中插入新节点的方法的空间复杂度是多少？
该方法的空间复杂度为O(1)。
如何表示链表及其随机指针？
链表的每个节点表示为一个包含值和随机指针索引的对，格式为[val, random_index]。
深拷贝链表的最终步骤是什么？
最终步骤是标记下一个节点并提取最终结果。
➡️
