My short python solution with O(n) space complexity, could I do better?

  • 1

    This solution makes a map between new members of the node class and existing members so the space complexity is O(n), although AFAIK, that's unavoidable since a deep copy must replicated the objects in the first palace. As best as I can tell, the solution is O(n) time.

    If anybody can elaborate on space complexity that would be really helpful, I know that I am probably not seeing something important here.

    def make_copy(node, tracker):
        # Base cases: None or existing nodes are returned w/o recursion
        if node is None:
            return None
        elif node in tracker:
            return tracker[node]
        # Make new node instance and map it to the old node
        newnode = RandomListNode(node.label)
        tracker[node] = newnode
        # recursively copy the next and random pointers before return = make_copy(, tracker)
        newnode.random = make_copy(node.random, tracker)
        return newnode
    class Solution:
        # @param head, a RandomListNode
        # @return a RandomListNode
        def copyRandomList(self, head):
            allnodes = {}
            newhead = make_copy(head, allnodes)
            return newhead

  • 0

    your code are so short. It's easy to understand . below is my code. It's too much line code than you.
    but I think there is no need so much recursion call.

    class Solution:
        # @param head, a RandomListNode
        # @return a RandomListNode
        def __init__(self):
            self.nodeMap = {}
        def copyRandomList(self, head):
            nodeMap = self.nodeMap
            randomList = []
            if head == None:
                return None
            temp = head
            nHead = None
            nPrev = None
            while temp != None:
                node = RandomListNode(temp.label)
                if temp not in nodeMap:
                    nodeMap[temp] = node
                if temp.random != None:
                    if temp.random not in nodeMap:
                        node.random = nodeMap[temp.random]
                if nHead == None:
                    nHead = node
                    nPrev = node
           = node
                    nPrev =
                temp =
            while randomList != []:
                node, srcNode = randomList.pop()
                if srcNode.random not in nodeMap:
                    node.random = self.copyRandomList(srcNode.random)
                    node.random = nodeMap[srcNode.random]
            return nHead

  • 0

    I made almost the same solution, but it failed to pass one very long input.
    So I just copy your code, it meets the same problem.

    class Solution:
        # @param head, a RandomListNode
        # @return a RandomListNode
        def __init__(self):
            self.all = {}
        def copyRandomList(self, head):
            if not head:
            new = RandomListNode(head.label)
            self.all[head] = new
            if in self.all:
       = self.all[]
       = self.copyRandomList(
            if head.random in self.all:
                new.random = self.all[head.random]
                new.random = self.copyRandomList(head.random)
            return new

Log in to reply

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