"""
# 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
# 复制节点
cur = head
while cur:
cur_copy = Node(cur.val)
cur_copy.next = cur.next
cur.next = cur_copy
cur = cur_copy.next
# 构造random
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
# 拆分链表
cur = head
new_head = cur.next
while cur.next:
temp = cur.next
cur.next = temp.next
cur = temp
return new_head