Share my Python solution, single scan, O(n) time and space complexity

  • 0

    The idea is simple: while checking a node, create copy for it AND the node that its random pointer points to, if they are not in the hash table.

    class Solution:
        # @param head, a RandomListNode
        # @return a RandomListNode
        def copyRandomList(self, head):
            dummy, current, mapping = RandomListNode(0), head, {None: None}
            prev  = dummy
            while current:
                if current in mapping:
                    node = mapping[current]
                    # create new node
                    node = RandomListNode(current.label)
                    # add mapping of current into dictionary
                    mapping[current] = node
                if current.random in mapping:
                    node.random = mapping[current.random]
                    node.random = RandomListNode(current.random.label)
                # connect new list
      , prev = node, node
                current =

Log in to reply

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