Simple Python solution, beats 95%, O(n) time


  • 0
    G
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if head == None:
            return None
        if head.next == None:
            newHead = RandomListNode(head.label)
            if head.random != None:
                newHead.random = newHead
            return newHead
            
        nodeDict = self.buildNodeDict(head)
        newNodeDict = dict()
        newHead = RandomListNode(head.label)
        
        # constract the normal list structure, consider the random pointers later.
        # firstly, build a new dict for the copy of random list, get a copy of 
        # each node in the original list
        p = head
        while p != None:
            newNodeDict[nodeDict[p]] = RandomListNode(p.label)
            p = p.next
        # link the list       
        for k, v in newNodeDict.items():
            if k != len(nodeDict)-1:
                v.next = newNodeDict[k+1]
        # now consider the random pointers
        p = head
        while p != None:
            if p.random != None:
                newNodeDict[nodeDict[p]].random = newNodeDict[nodeDict[p.random]]
            p = p.next
        
        return newNodeDict[0]
        
        
    def buildNodeDict(self, head):
        nodeDict = dict()
        i = 0
        while head != None:
            nodeDict[head] = i
            head = head.next
            i += 1
            
        return nodeDict

Log in to reply
 

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