Straight forward O(n) time & space solution


  • 0
    Z
    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 = tmp.next
            copied_head = self.index[head.label]
            while head:
                ref = self.index[head.label]
                ref.next = head.next and self.index[head.next.label]
                ref.random = head.random and self.index[head.random.label]
                head = head.next
            return copied_head
    

Log in to reply
 

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