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 not in dic:
                        dic[] = RandomListNode(
           = dic[]
                if head.random:
                    if head.random not in dic:
                        dic[head.random] = RandomListNode(head.random.label)
                    tcopy.random = dic[head.random]
                head =
            return copy

Log in to reply

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