- 题目描述
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 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]]
示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
- 解法一：DFS深度优先
这道题的考点在链表的深拷贝和浅拷贝。
在Python中其实可以用一句话就实现深拷贝
class Solution: def copyRandomList(self, head: 'Node') -> 'Node': return copy.deepcopy(head)
dfs其实就是递归求解。
首先我们先判断递归结束条件：当此时节点为空结束，返回None
调用递归：创建新节点copy，copy的next为递归head的next节点，copy的random为递归head的random节点，返回copy即可。
附加条件：当递归调用某个节点已经被拷贝，即已经出现在visited这个hash表中（说明之前已经拷贝过），则不需要拷贝，直接返回这个节点即可。
""" # 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: 'Node') -> 'Node': def recur(head): if not head: return if head in visitisted: return visitisted[head] copy = Node(head.val, None, None) visitisted[head] = copy copy.next = recur(head.next) copy.random = recur(head.random) return copy visitisted = {} return recur(head)
- 解法二：BFS广度优先搜索
广度优先我们通常都是用队列实现的。
1.我们首先创建hash表保存已经拷贝的节点（{原节点：拷贝节点}）
2.创建队列，并将head入队
3.当队列不为空，弹出一个节点，如果该节点的next没有被拷贝，则拷贝该节点的next节点，如果该节点的random节点没被拷贝过，则拷贝random节点
""" # 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 """ from collections import deque class Solution: def copyRandomList(self, head: 'Node') -> 'Node': ''' bfs解法：队列 ''' if not head: return res = {} dq = deque() dq.append(head) copy = Node(head.val, None, None) res[head] = copy while dq: tmp = dq.pop() if tmp.next and tmp.next not in res: res[tmp.next] = Node(tmp.next.val, None, None) # res[tmp.next] = tmp.next dq.append(tmp.next) if tmp.random and tmp.random not in res: res[tmp.random] = Node(tmp.random.val, None, None) # res[tmp.random] = tmp.random dq.append(tmp.random) res[tmp].next = res.get(tmp.next) res[tmp].random = res.get(tmp.random) return copy
时间复杂度：O(N)
空间复杂度：O(N)