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

  • 0

    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 not in mapping:
                    mapping[] = RandomListNode(
                mapping[curr].next = mapping[]
            if curr.random:
                if curr.random not in mapping:
                    mapping[curr.random] = RandomListNode(curr.random.label)
                mapping[curr].random = mapping[curr.random]
            curr =
        return mapping[head]

Log in to reply

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