Simple clean O(n) Python solution beats 81%

  • 0

    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 exist, and 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 exist, and 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
    # = None
    #         self.random = None
    class Solution(object):
        def copyRandomList(self, head):
            :type head: RandomListNode
            :rtype: RandomListNode
            if head == None:
            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 !=None:
                if id( not in visitD:
                    nextN = RandomListNode(0)
           = nextN
                    self.copyRandomListUtil(,, visitD)
           = visitD[id(]
            if head.random !=None:
                if id(head.random) not in visitD:
                    randomN = RandomListNode(0)
                    currNode.random = randomN
                    self.copyRandomListUtil(head.random, currNode.random, visitD)
                    currNode.random = visitD[id(head.random)]

Log in to reply

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