Python 2 pass with hashtable O(n)


  • 0
    A
    def copyRandomList(self, head):
        old_head = head
        if not head:
            return head
        node_dic = {}
        VeryRoot = RandomListNode(0)
        root = VeryRoot
        
        while head:
            nextNode = RandomListNode(head.label)
            node_dic[head] = nextNode
            root.next = nextNode
            root = root.next
            head = head.next
        
        head = old_head
        root = VeryRoot.next
        while head:
            randomNode = head.random
            if randomNode:
                root.random = node_dic[randomNode]
            head = head.next
            root = root.next
        
        return VeryRoot.next

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.