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


  • 0
    D

    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]
                else:
                    # 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]
                else:
                    node.random = RandomListNode(current.random.label)
                # connect new list
                prev.next, prev = node, node
                current = current.next
            return dummy.next

Log in to reply
 

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