Python simple dict solution with O(n) time

  • 2

    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 =
            #second iteration to copy two pointers
            itr = head
            while itr is not None:
                node = table[id(itr)]
       = table[id(]
                node.random = table[id(itr.random)]
                itr =
            return table[id(head)]

Log in to reply

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