题目描述
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。 来源：力扣（LeetCode）
解题思路
剑指书上的方法
1.方法一
第一步：复制原始链表上的每个节点N、创造N’ ; 把创造出来的节点用 m_pnext链接起来; 把<N,N’>放进哈希表。第二步：设置复制链表上的 m_psibling 。如果原始链表节点N的 m_psibling 指向节点S; 复制链表当中的 N’ 指向 S’ 。
2.方法二
第一步：复制链表的节点，将复制的节点接到原始节点的后面 e.g. 1 -> 1’ -> 2 -> 2’ -> 3 -> 3’第二步：将链表复制节点的 random 指向的指针 (n.next.random)，指向原始节点的后面 (n.random.next)
Leetcode上的方法
题意的复制是指『深拷贝』（Deep Copy）<=> 浅拷贝（Shallow Copy）
浅拷贝只复制了某个对象的指针，而不复制对象本身，共享同一块内存。 => newhead = head （这只是将指针指到了 head）深拷贝要创造一个一模一样的对象，新对象跟旧对象不共享内存，修改新对象不会改到原对象。
用 DFS（Depth-First Search）的递归解法
将已经存在的节点存入 Hash Table。从最深的一个节点开始复制。在写逻辑的时候，思考最后一步的要件（判断逻辑 & 返回），递归解法都是如此操作。
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:
def copyRandomList(self
, head
: 'Node') -> 'Node':
"""
剑指方法二
"""
if not head
:
return None
n
= head
while n
:
node
= Node
(n
.val
)
node
.next = n
.next
n
.next = node
n
= node
.next
n
= head
while n
:
if not n
.random
:
n
.next.random
= None
else:
n
.next.random
= n
.random
.next
n
= n
.next.next
n
= head
.next
while n
.next:
n
.next = n
.next.next
n
= n
.next
return head
.next
"""
Leetcode方法：用DFS解
"""
def dfs(head
):
if not head
:
return None
if head
in visited
:
return visited
[head
]
copy
= Node
(head
.val
)
visited
[head
] = copy
copy
.next = dfs
(head
.next)
copy
.random
= dfs
(head
.random
)
return copy
visited
= {}
return dfs
(head
)
