195 - 138 复制带随机指针的链表

题目

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

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

示例：

img

输入： {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

解释： 节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。 节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。

提示：

1. 你必须返回给定头的拷贝作为对克隆列表的引用。

解答

哈希表+递归

跟着next指针或者random指针。没有就新建

然后把经过的指针记录在哈希表里面

https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/fu-zhi-dai-sui-ji-zhi-zhen-de-lian-biao-by-leetcod/

class Solution:
    def __init__(self):
        self.visited = {}

    def copyRandomList(self, head: 'Node') -> 'Node':
        if head == None:
            return None
        if head in self.visited:
            return self.visited[head]
        node = Node(head.val, None,None)
        self.visited[head] = node
        node.next = self.copyRandomList(head.next)
        node.random = self.copyRandomList(head.random)
        return node

Runtime: 32 ms, faster than 91.16% of Python3 online submissions for Copy List with Random Pointer.

Memory Usage: 13.3 MB, less than 100.00% of Python3 online submissions for Copy List with Random Pointer.

迭代

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return head
        ptr = head
        while ptr:
            new_node = Node(ptr.val, None, None)
            new_node.next = ptr.next
            ptr.next = new_node
            ptr = new_node.next
        ptr = head
        while ptr:
            ptr.next.random = ptr.random.next if ptr.random else None
            ptr = ptr.next.next
        ptr_old_list = head
        ptr_new_list = head.next
        head_old = head.next
        while ptr_old_list:
            ptr_old_list.next = ptr_old_list.next.next
            ptr_new_list.next = ptr_new_list.next.next if ptr_new_list.next else None
            ptr_old_list = ptr_old_list.next
            ptr_new_list = ptr_new_list.next
        return head_old

Runtime: 36 ms, faster than 74.20% of Python3 online submissions for Copy List with Random Pointer.

Memory Usage: 13.1 MB, less than 100.00% of Python3 online submissions for Copy List with Random Pointer.