mq006.复制带随机指针的列表

"""
# 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 copyRandomList1(self, head: 'Node') -> 'Node':
        self.visited = {}        
        return self.dfs(head)

    def dfs(self, node):
        if not node:
            return None
        if node in self.visited:
            return self.visited[node]
        copy = Node(node.val, None, None)
        self.visited[node] = copy
        copy.next = self.dfs(node.next)
        copy.random = self.dfs(node.random)
        return copy

    def copyRandomList2(self, head: 'Node') -> 'Node':
        if not head:
            return None

        cur = head
        while cur:
            new_node = Node(cur.val, None, None)
            new_node.next = cur.next
            cur.next = new_node
            cur = new_node.next
        
        cur = head
        while cur:
            cur.next.random = cur.random.next if cur.random else None
            cur = cur.next.next
        
        cur_old = head
        cur_new = new_head = head.next
        while cur_old:
            cur_old.next = cur_old.next.next
            cur_new.next = cur_new.next.next if cur_new.next else None
            cur_old = cur_old.next
            cur_new = cur_new.next
        return new_head