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

https://leetcode-cn.com/problems/copy-list-with-random-pointer/

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。

通过次数36,172 | 提交次数67,426

First Try

2020-07-07

重点是，dict竟然能够用node作为字典key。其实如果不行的话，直接使用id(node)内存地址来也行。

之前做过图的深度复制，这道应该说更简单了，结果还是花了过多时间。没想到random的指向并没有idx之类的标记，指向的就是node内存本身了。所以只能上字典映射了。

"""
# Definition for a Node.
class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """

        # 重点是，dict竟然能够用node作为字典key。其实如果不行的话，直接使用id(node)内存地址来也行。
        if not head:
            return head 
        dummy = node = Node(-1)
        node.next = head
        moc = dict({dummy: Node(-1)})  # map of cache

        while node.next:
            if not moc.get(node.next):
                moc[node.next] = Node(node.next.val)
            moc[node].next = moc[node.next]
            if node.next.random:
                if not moc.get(node.next.random, None):
                    moc[node.next.random] = Node(node.next.random.val)
                moc[node.next].random = moc[node.next.random]
                
            node = node.next 
            # print(node)

        return moc[head]

执行用时：48 ms, 在所有 Python 提交中击败了87.84%的用户
内存消耗：13.4 MB, 在所有 Python 提交中击败了100.00%的用户

138. 复制带随机指针的链表​

First Try​

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

First Try