Python simple dict solution with O(n) time


  • 2
    L

    Basically iterating over the list twice.

    class Solution(object):
        def copyRandomList(self, head):
    
            if head is None:
                return None
            
            #hash table to mark down original codes
            table = {}
            table[id(None)] = None
            
            #first iteration to copy list without pointers
            itr = head
            while itr is not None:
                #save corresponding node with id()
                table[id(itr)] = RandomListNode(itr.label)
                itr = itr.next
            
            #second iteration to copy two pointers
            itr = head
            while itr is not None:
                node = table[id(itr)]
                node.next = table[id(itr.next)]
                node.random = table[id(itr.random)]
                itr = itr.next
            
            return table[id(head)]
    

Log in to reply
 

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