138. Copy List with Random Pointer

Problem Link

To create a deep copy of the linked list, we use a hash map to maintain a one-to-one mapping between each original node and its cloned node.

In the first pass, we iterate through the original list and create a new node for each existing node, storing the mapping from the original node to its clone in the hash map. At this stage, only the node values are copied.

In the second pass, we iterate through the list again and assign the Next and Random pointers for each cloned node by looking them up in the hash map. This ensures that both pointers correctly reference the corresponding cloned nodes.

Finally, we return the cloned head node obtained from the hash map, which represents the deep-copied list.

Runtime Complexity

Time: \(O(n)\)

Space: \(O(n)\)

PythonGo

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        copyList = dict()
        copyList[None] = None
        curr = head
        while curr:
            copyList[curr] = Node(curr.val)
            curr = curr.next

        copyCurr, curr = copyList[head], head
        while curr:
            copyCurr.next = copyList[curr.next]
            copyCurr.random = copyList[curr.random]
            curr = curr.next
            copyCurr = copyCurr.next
        return copyList[head]

func copyRandomList(head *RandomListNode) *RandomListNode {
    clone := make(map[*RandomListNode]*RandomListNode)
    curr := head
    for curr != nil {
        clone[curr] = &RandomListNode{Val: curr.Val}
        curr = curr.Next
    }

    curr = head
    cloneCurr, _ := clone[curr]
    for curr != nil {
        cloneCurr.Next, _ = clone[curr.Next]
        cloneCurr.Random, _ = clone[curr.Random]
        curr = curr.Next
        cloneCurr = cloneCurr.Next
    }
    res, _ := clone[head]
    return res
}

---