[数据结构与算法]剑指 Offer 35. 复杂链表的复制

请实现 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]]

"""
# 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 
        #1.复制节点的val，并且放到原节点的后面
        cur=head
        while cur:
            curcopy=Node(cur.val) #构造副本的值
            curcopy.next=cur.next#插入到源节点的后面
            cur.next=curcopy #修改源节点的值
            cur=curcopy.next  #cur 移动到原来链表的后一个节点
        
        #2.构造random
        cur=head
        while cur:
            if cur.random:
                cur.next.random=cur.random.next  #把后续节点指向随机节点的下一个节点
            cur=cur.next.next  #cur后面是copy，只需遍历原节点

        #3.拆分链表
        cur=head
        newhead=head.next #需要一个节点来记录返回
        while cur.next:
            tmp=cur.next #暂存记录下一节点
            cur.next=tmp.next
            cur=tmp
            
        return newhead