Construct a Deep Copy of LinkedList

Given a linked list where each node contains an additional random pointer that could point to any node in the list or null, we need to create a deep copy of the list.

Consider an example to illustrate this.

Original List

Node1(val=1) -> Node2(val=2) -> Node3(val=3)

With random pointers

• Node1.random: Node3
• Node2.random: Node1
• Node3.random: Node2

The new list will look like this.

NewNode1(val=1) -> NewNode2(val=2) -> NewNode3(val=3)

With random pointers

• NewNode1.random: NewNode3
• NewNode2.random: NewNode1
• NewNode3.random: NewNode2

The new list shouldn't have any reference to the node of the original list.

public Node CopyRandomList(Node head)
{
    if (head == null) return null;
    Dictionary<Node, Node> keyValuePairs = new Dictionary<Node, Node>();
    Node curr = head;
    while (curr != null)
    {
        keyValuePairs[curr] = new Node(curr.val);
        curr = curr.next;
    }
    curr = head;
    while (curr != null)
    {
        keyValuePairs[curr].next = curr.next == null ? null : keyValuePairs[curr.next];
        keyValuePairs[curr].random = curr.random == null ? null : keyValuePairs[curr.random];
        curr = curr.next;
    }
    return keyValuePairs[head];
}

Step-by-Step Breakdown

1. Initialization: A dictionary key-value pair is created to map original nodes to their corresponding new nodes.
2. First Pass: Creating New Nodes.
   • Traverse the original list and create new nodes with the same value as the original nodes.
   • Store these new nodes in the dictionary with the original nodes as keys.
3. Second Pass: Setting Next and Random Pointers.
   • Traverse the original list again.
   • For each original node, set the next and random pointers of the corresponding new node using the dictionary.
4. Return the Head of the New List: Return the new head node from the dictionary.
   

Conclusion

This approach ensures that we create a deep copy of the linked list with random pointers in O(n) time complexity and O(n) space complexity. The use of a dictionary helps in efficiently mapping original nodes to their corresponding new nodes, making the process straightforward and easy to understand.