[leetcode] 138. 随机链表的复制 Copy List with Random Pointer

给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。例如如果原链表中有 X 和 Y 两个节点其中 X.random -- Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random -- y 。返回复制链表的头节点。用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示val一个表示 Node.val 的整数。random_index随机指针指向的节点索引范围从 0 到 n-1如果不指向任何节点则为 null 。你的代码 只 接受原链表的头节点 head 作为传入参数。示例 1输入head [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出[[7,null],[13,0],[11,4],[10,2],[1,0]]示例 2输入head [[1,1],[2,1]] 输出[[1,1],[2,1]]示例 3输入head [[3,null],[3,0],[3,null]] 输出[[3,null],[3,0],[3,null]]提示0 n 1000-104 Node.val 104Node.random 为 null 或指向链表中的节点。Python这道题我想复杂了没想到用一个哈希表就能解决递归遍历的时候注意把遍历的节点存入到哈希表即可然后注意递归的终止条件以及继续递归的条件思路很直接我大意了哈哈。 # Definition for a Node. class Node: def __init__(self, x: int, next: Node None, random: Node None): self.val int(x) self.next next self.random random class Solution: node_map {} def copyRandomList(self, head: Optional[Node]) - Optional[Node]: if head is None: return head if head not in self.node_map: new_node Node(head.val) self.node_map[head]new_node new_node.next self.copyRandomList(head.next) new_node.random self.copyRandomList(head.random) return self.node_map[head]下面是一个非递归的版本 # Definition for a Node. class Node: def __init__(self, x: int, next: Node None, random: Node None): self.val int(x) self.next next self.random random class Solution: def copyRandomList(self, head: Optional[Node]) - Optional[Node]: dummy Node(-1) p head mapping {} p1 dummy while p: if p in mapping: new_node mapping[p] else: new_node Node(p.val) mapping[p]new_node p1.next new_node rand_node p.random if rand_node is not None: if rand_node in mapping: new_node.random mapping[rand_node] else: new_node.random Node(rand_node.val) mapping[rand_node]new_node.random p p.next p1 p1.next return dummy.next