三个月算法进阶--day65

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        def dfs(node):
            if not node:
                return
            clone = Node(node.val)
            if node in visited:
                return visited[node]
            visited[node] = clone
            visited[node].next = dfs(node.next)
            visited[node].random = dfs(node.random)
            return visited[node]
        visited = {}
        return dfs(head)

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        visited = {}
    
        def bfs(head):
            if not head: return head
            clone = Node(head.val, None, None)
            queue = collections.deque()
            queue.append(head)
            visited[head] = clone
            while queue:
                tmp = queue.pop()
                if tmp.next and tmp.next not in visited:
                    visited[tmp.next] = Node(tmp.next.val, [], [])
                    queue.append(tmp.next)  
                if tmp.random and tmp.random not in visited:
                    visited[tmp.random] = Node(tmp.random.val, [], [])
                    queue.append(tmp.random)
                visited[tmp].next = visited.get(tmp.next)
                visited[tmp].random = visited.get(tmp.random)
            return clone
        return bfs(head)

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return head
        cur = head
        while cur:
            new_node = Node(cur.val)
            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_new_list = head.next
        new_head = head.next
        while cur_new_list:
            cur_new_list.next = cur_new_list.next.next if cur_new_list.next else None
            cur_new_list = cur_new_list.next
        return new_head