Simple clean O(n) Python solution beats 81%


  • 0
    Y

    My general approach is to understand this as a tree and do in oder tree traversal. That is head -> next -> random.

    Initially, I pass in a created new node with value zero as current node.

    When processing head of the old linkedlist, assign its value to the current node.
    Add the id of head to a dictionary as key and value as the current node object.

    If head.next exist, and head.next id is not in the dictionary, create new node with value zero and assign it as the next of the current node. Then do recursion with head next, current node next.

    If head.next exist, and head.next id is in the dictionary, we just set the current node next to the value of the corresponding key in dictionary.

    Same as random.

    Since its an in order traversal, we going through the list once with O(n). Space complexity O(n) as well.

    # Definition for singly-linked list with a random pointer.
    # class RandomListNode(object):
    #     def __init__(self, x):
    #         self.label = x
    #         self.next = None
    #         self.random = None
    
    class Solution(object):
        def copyRandomList(self, head):
            """
            :type head: RandomListNode
            :rtype: RandomListNode
            """
            if head == None:
                return
    
            currNode = RandomListNode(0)
            visitD = {}
            self.copyRandomListUtil(head, currNode, visitD)
            return currNode
            
        def copyRandomListUtil(self, head, currNode, visitD):
    
            currNode.label = head.label
            visitD[id(head)] = currNode
    
            if head.next !=None:
                if id(head.next) not in visitD:
                    nextN = RandomListNode(0)
                    currNode.next = nextN
                    self.copyRandomListUtil(head.next, currNode.next, visitD)
                else:
                    currNode.next = visitD[id(head.next)]
            if head.random !=None:
                if id(head.random) not in visitD:
                    randomN = RandomListNode(0)
                    currNode.random = randomN
                    self.copyRandomListUtil(head.random, currNode.random, visitD)
                else:
                    currNode.random = visitD[id(head.random)]
            
            return
            
    

Log in to reply
 

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