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