Screen Shot 2021-03-12 at 10.36.11 AM.png
方法一：拼接 + 拆分
-
构建拼接链表Screen Shot 2021-03-12 at 10.37.47 AM.png
2.构建所有random连接
Screen Shot 2021-03-12 at 10.38.29 AM.png -
拆分
Screen Shot 2021-03-12 at 10.39.24 AM.png
实现：
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head: return
cur = head
# 1. 复制各节点，并构建拼接链表
while cur:
tmp = Node(cur.val)
tmp.next = cur.next
cur.next = tmp
cur = tmp.next
# 2. 构建各新节点的 random 指向
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
# 3. 拆分两链表
cur = res = head.next
pre = head
while cur.next:
pre.next = pre.next.next
cur.next = cur.next.next
pre = pre.next
cur = cur.next
pre.next = None # 注意单独处理原链表尾节点
return res # 返回新链表头节点
方法 二：哈希表
利用哈希表的查询特点，考虑构建 原链表节点 和 新链表对应节点 的键值对映射关系，再遍历构建新链表各节点的 next 和 random 引用指向即可。
Screen Shot 2021-03-12 at 10.42.11 AM.png
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head: return
dic = {}
# 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
cur = head
while cur:
dic[cur] = Node(cur.val)
cur = cur.next
cur = head
# 4. 构建新节点的 next 和 random 指向
while cur:
dic[cur].next = dic.get(cur.next)
dic[cur].random = dic.get(cur.random)
cur = cur.next
# 5. 返回新链表的头节点
return dic[head]
