Straight forward O(n) time & space solution

  • 0
    1. Make a copy of every node without considering next and random reference and store in the hashtable

    2. Since all copied nodes are stored in the hashtable by reference, we just need another pass to every object to fix the reference.

    class Solution(object):
        def copyRandomList(self, head):
            if not head: return
            self.index = {}
            tmp = head
            while tmp:
                copynode = RandomListNode(tmp.label)
                self.index[tmp.label] = copynode
                tmp =
            copied_head = self.index[head.label]
            while head:
                ref = self.index[head.label]
       = and self.index[]
                ref.random = head.random and self.index[head.random.label]
                head =
            return copied_head

Log in to reply

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