Python O(n) solution with dictionary, one iteration.


  • 0
    L

    Didn't find a Python version with one iteration, but it's definitely doable.
    Same idea as Clone Graph, find the links -> copy the nodes -> copy the links.

    def copyRandomList(self, head):
        if not head:
            return None
        mapping = {}  # original node => copied node
        mapping[head] = RandomListNode(head.label)
        
        curr = head
        while curr:
            if curr.next:
                if curr.next not in mapping:
                    mapping[curr.next] = RandomListNode(curr.next.label)
                mapping[curr].next = mapping[curr.next]
            if curr.random:
                if curr.random not in mapping:
                    mapping[curr.random] = RandomListNode(curr.random.label)
                mapping[curr].random = mapping[curr.random]
            curr = curr.next
    
        return mapping[head]
    

Log in to reply
 

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