Python O(n) Solution


  • 0
    J
    # 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 not head:
                return None
            
            d = {}
            node = head
            prev = None
            newHead = None
            while node:
                if node not in d:
                    d[node] = RandomListNode(node.label)
                newNode = d[node]
                if prev:
                    prev.next = newNode
                else:
                    newHead = newNode
                prev = newNode
    
                if node.random:
                    if node.random not in d:
                        d[node.random] = RandomListNode(node.random.label)
                    newNode.random = d[node.random]
                
                node = node.next
            
            return newHead
    

Log in to reply
 

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