使用随机指针复制列表
“使用随机指针复制列表”问题的详细指南和 Python 实现。
1. 学习
“使用随机指针复制列表”问题是链接列表部分的一个关键挑战。
此实现侧重于 Python 中的简单级逻辑。
在我们提供的解决方案中，我们优先考虑技术准确性和代码可读性。
2. Real-World Applications
3. Visual Intuition
可视化带有随机指针的复制列表的逻辑流程。
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
仔细阅读带有随机指针的复制列表的问题陈述。
2. Formulate brute force
起草一个简单的迭代解决方案。
3. Identify inefficiency
寻找冗余计算。
4. Optimize search path
使用散列或排序来加速该过程。
5. Final Implementation
清理生产标准代码。
问题陈述
给出一个长度为 n 的链表，使得每个节点都包含一个附加的随机指针，该指针可以指向链表中的任何节点，也可以指向 null。
构建列表的深层副本。深度副本应该由 n 个全新节点组成，其中每个新节点的值设置为其对应的原始节点的值。新节点的下一个指针和随机指针都应指向复制列表中的新节点，使得原始列表和复制列表中的指针表示相同的列表状态。
该列表表示为 [val, random_index] 对的列表，其中 random_index 是随机指针指向的节点的索引，如果指向 null，则为 -1。实现一个函数 copyRandomList(head: list) -> list 以相同的格式返回深层副本。
- •0 <= n <= 1000
- •-10000 <= Node.val <= 10000
- •Node.random is null or points to some node in the linked list
示例
[[7,-1],[13,0],[11,4],[10,2],[1,0]]
[[7,-1],[13,0],[11,4],[10,2],[1,0]]
The deep copy has the same structure. Node 0 (val=7) has random=null, Node 1 (val=13) has random pointing to Node 0, etc.
[[1,1],[2,1]]
[[1,1],[2,1]]
Node 0 (val=1) has random pointing to Node 1. Node 1 (val=2) has random pointing to Node 1 (itself).
[[3,-1],[3,0],[3,-1]]
[[3,-1],[3,0],[3,-1]]
Three nodes all with value 3. Node 1's random points to Node 0.
Need a Hint?
Edge Cases to Watch
- 空输入结构
- 单元素输入
- 大数值范围
准备好解决了吗？
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
面试见解和变化
复杂性分析分解
为什么时间: Directly evaluates all possibilities.
为什么选择太空: Uses standard local memory.
为什么时间: Optimized paths reduce total operations.
为什么选择太空: May trade memory for speed.
优化解决方案Python代码
优化解决方案Python代码
def copy_random_list_opt(head):
if not head: return None
if isinstance(head, list):
# Already in list format, return a deep copy
import copy
return copy.deepcopy(head)
return head暴力破解代码（剧透保护）
暴力破解代码（剧透保护）
def copy_random_list_brute(head):
if not head: return None
# Map node indices to list of pairs format
if isinstance(head, list):
# Already in list format, return a deep copy
import copy
return copy.deepcopy(head)
return headAlgorithm Pattern Checklist
When dealing with Linked List data patterns.
- Are constraints clear?
- Is there a linear or logarithmic optimization possible?
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
推荐的 Python 资源
通过相关的交互式教程、备忘单和代码比较来扩展您的知识。
Python 列表：数组、方法和迭代
了解有关 Python 列表的所有内容。了解如何在 Python 中原生创建、切片、修改和迭代数组。
如何在 Python 中对列表进行排序（升序和降序）
了解如何在 Python 中使用 sort() 方法和sorted() 函数对列表进行排序。发现自定义键排序和逆序示例。
Python 列表方法备忘单
Python 列表操作快速参考指南。掌握附加、插入、删除、排序和切片元素。
Python 与 JavaScript：哪种编程语言最好？
Python 和 JavaScript 的全面比较。探索语法差异、性能、用例（后端与前端）和编码示例。