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

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

中文English

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

返回一个深拷贝的链表。 

挑战

可否使用O(1)的空间

hashmap写法，O(n)时间复杂度

"""
Definition for singly-linked list with a random pointer.
class RandomListNode:
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None
"""


class Solution:
    # @param head: A RandomListNode
    # @return: A RandomListNode
    def copyRandomList(self, head):
        # write your code here
        #hashmap来存储，label
        
        root = head
        mapping = {}
        while head:
            mapping[head] = RandomListNode(head.label)
            head = head.next
            
        for node in mapping:
            if node.next:
                mapping[node].next = mapping[node.next]
            if node.random:
                mapping[node].random = mapping[node.random]
        
        return mapping[root]