138. 复制带随机指针的链表(Medium)

题目描述

Leetcode 地址、剑指 Offer 地址

类别

• 链表
• 哈希表
• dfs/bfs

解题思路

一、哈希表

• 使用哈希表，将旧的地址与新的地址关联起来

  注意，这里的新的表，next 和 random 都没有创建好的就是，就存入了哈希表

  利用的是 Python 哈希表存入的是引用（地址）的原理

代码

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        def copy(node):
            if not node:return node
            if not node in visited:
                visited[node] = Node(node.val)
            return visited[node]
        
        if not head: return head 
        old = head 
        new = Node(old.val)
        visited = {}
        visited[old] = new 

        while old:
            new.next = copy(old.next)
            new.random = copy(old.random)
            old = old.next
            new = new.next 
        return visited[head]

二、DFS

代码

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        def dfs(node):
            if not node: 
                return node 
            if node in visited:
                return visited[node]
            new_node = Node(node.val)
            visited[node] = new_node  # 这句一定要在 递归语句之前，不然会存在反复创建的问题
            new_node.next = dfs(node.next)
            new_node.random = dfs(node.random)
            return new_node
        visited = {}
        return dfs(head)

func dfs(root *Node, visited  map[*Node] *Node) *Node {
    if root == nil {
        return root 
    }

    v, ok := visited[root]
    if ok {
        return v
    }

    new_node := &Node{Val:root.Val}
    visited[root] = new_node
    new_node.Next = dfs(root.Next, visited)
    new_node.Random = dfs(root.Random, visited)
    return new_node
}

func copyRandomList(head *Node) *Node {
   visited := make(map[*Node] *Node)
   return dfs(head, visited) 
}

三、BFS

这里使用BFS不是那么合适，BFS一般用于求最短路径等问题。但是也提供此版本代码

代码

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