Python + Dictionary


  • 0

    This problem is very similar to 133. Clone Graph, and I AC this problem right after coding while three time for 133. Clone Graph. The ironic part is that this question is tagged HARD, and 133. Clone Graph is tagged MEDUIM. So sometimes the difficulty they tagged is not that "accurate". UPDATE: I notice others can solve this problem with O(1) extra space, maybe that will be the "HARD" part.

    class Solution(object):
        def copyRandomList(self, head):
            if not head:
                return head
            copy = RandomListNode(head.label)
            dic = {head: copy}
            while head:
                tcopy = dic[head]
                if head.next:
                    if head.next not in dic:
                        dic[head.next] = RandomListNode(head.next.label)
                    tcopy.next = dic[head.next]
                if head.random:
                    if head.random not in dic:
                        dic[head.random] = RandomListNode(head.random.label)
                    tcopy.random = dic[head.random]
                head = head.next
            return copy
    

Log in to reply
 

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