题目链接
题目描述：
请实现 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。
解题思路：
原地修改链表 1.在每个节点后面复制一个节点 2.复制每个节点的random指针（注意random指向none的情况，不一定是最后一个节点的random指向none） 3.将该链表拆成两个
class Solution: def copyRandomList(self, head: 'Node') -> 'Node': if not head : return h1=h2=h3=head while h1:#复制节点 node=Node(h1.val) node.next=h1.next h1.next=node h1=node.next #把node放在h后面之后，h向后移应该指向node的next while h2:#复制random链接 if h2.random is None: h2.next.random=None else: h2.next.random=h2.random.next h2=h2.next.next hclone=tmp=head.next while h3:#将复制的节点与原节点拆成两个链表 h3.next=tmp.next h3=h3.next if not h3: break tmp.next=h3.next tmp=tmp.next return hclone方法二： 采用字典存储原节点和复制节点的映射关系 再次遍历链表，将原节点的next和random赋给复制节点 由于random的指向可能为none，但是字典中并没有none的映射关系，所以单独进行处理
dic={} cur=head while cur: dic[cur]=Node(cur.val) cur=cur.next cur=head dic[None]=None while cur: dic[cur].next=dic[cur.next] dic[cur].random=dic[cur.random] cur=cur.next return dic[head]