0138. 复制带随机指针的链表 #
- 标签:链表、哈希表
- 难度:中等
题目大意 #
描述:给定一个链表的头节点 head
,链表中每个节点除了 next
指针之外,还包含一个随机指针 random
,该指针可以指向链表中的任何节点或者空节点。
要求:将该链表进行深拷贝。返回复制链表的头节点。
说明:
- $0 \le n \le 1000$。
- $-10^4 \le Node.val \le 10^4$。
Node.random
为null
或指向链表中的节点。
示例:
|
|
|
|
解题思路 #
思路 1:迭代 #
- 遍历链表,利用哈希表,以
旧节点: 新节点
为映射关系,将节点关系存储下来。 - 再次遍历链表,将新链表的
next
和random
指针设置好。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。