力扣刷题Day 34：随机链表的复制（138）

1.题目描述

2.思路

方法1：直接copy.deepcopy就可以了。

方法2：先遍历链表将结点及其索引存入node_dict，再遍历链表将当前结点索引与random的索引存入random_dict，然后遍历链表得到random均为空的新链表，遍历新链表将结点及其索引存入new_node_dict，最后根据random_dict修改新链表的random。

3.代码（Python3）

方法1：

class Solution:def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':return copy.deepcopy(head)

方法2：

class Solution:def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':# 原链表的结点索引node = headnode_dict = {}idx = 0while node:node_dict[node] = idxnode = node.nextidx += 1# 原链表的random与idx对应关系node = headrandom_dict = {}idx = 0while node:random_dict[idx] = node_dict[node.random] if node.random else -1node = node.nextidx += 1# 得到除了random的拷贝new_dummy = Node(0)node, new_node = head, new_dummywhile node:new_node.next = Node(node.val)node, new_node = node.next, new_node.next# 新链表的结点索引new_node = new_dummy.nextnew_node_dict = {}idx = 0while new_node:new_node_dict[idx] = new_nodenew_node = new_node.nextidx += 1# 根据原链表里random与idx的对应关系修改新链表for key, value in random_dict.items():if value != -1:new_node_dict[key].random = new_node_dict[value]return new_dummy.next

4.执行情况

方法1：

方法2：

5.感想

方法二的代码虽然繁琐但效率比方法一要高。