O(n) with a dictionary in Python


  • 0
    X
    class Solution(object):
        def copyRandomList(self, head):
            """
            :type head: RandomListNode
            :rtype: RandomListNode
            """
            d = {}; dummy = RandomListNode(0)
            p = head; newhead = dummy
            while p:
                newNode = RandomListNode(p.label)
                d[p] = newNode
                newhead.next = newNode
                newhead = newhead.next
                p = p.next
            
            p = head; newhead = dummy.next
            while p:
                if p.random:
                    newhead.random = d[p.random]
                p = p.next
                newhead = newhead.next
            return dummy.next

Log in to reply
 

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