Problem

This problem is about creating an exact copy of a given linked list where each node has a random pointer which can point to any node in the list or null.

In the example given, the linked list's input representation is in the form of a dictionary:

1
2
3{
4  "$id":"1",
5  "next": {
6    "$id":"2",
7    "next": null,
8    "random": {
9      "$ref":"2"
10    },
11    "val": 2
12  },
13  "random": {
14    "$ref":"2"
15  },
16  "val": 1
17}

In this case, there are two nodes ("$id": "1" and "$id": "2"), Node 1's value is 1, both of its next and random pointers point to Node 2. Node 2's value is 2, its next pointer points to null and its random pointer points to itself. The challenge is to return a new linked list that is a deep copy of this linked list, meaning that it contains new nodes with the same values and the same relative links as the original list.

Approach

The solution to the problem uses depth-first search (DFS) which is an algorithm for traversing or searching tree or graph data structures. The solution also utilizes a hash map to keep track of the nodes that have already been visited and copied.

In the first step, we check if the head of the linked list is null. If it is, we return null as we can't create a copy of an empty linked list.

Next, we check if the current node already exists in the map. If it does, it means we already created a copy of it, so we return the copy.

If the current node doesn't exist in the map, we create a copy of it, and add it to the map with the original node as the key and the copy as its value.

Once the node is created, we set its next and random pointers. We use recursion here to recursively copy the next and random nodes. The recursive calls also return the copied nodes which we set as the next and random pointers of the copied node.

Finally, we return the copied node.

Let's go through an example on how to make a deep copy of a linked list. Consider this linked list (LL):

1
2
3Original LL: 1 -> 2 -> 3 -> 4 -> 5
4Random Ptrs:
51->3
62->1
73->5
84->2
95->4

Now, let's follow the steps and make a deep copy of this list.

Step 1

Map the head node (Node 1) in the map, so our map becomes {1: 1'} where 1' is the deep copy of node 1.

Step 2

Repeat step 1 for Node 2. Map becomes {1: 1', 2: 2'}.

Step 3

Repeat for Nodes 3, 4, and 5. Final map is {1: 1', 2: 2', 3: 3', 4: 4', 5: 5'}.

Step 4

Now that all nodes have been copied, we can assign the next and random pointers.

Step 5

Finally, return the head of the copied list (1' in this case).

Let's see this approach applied in various languages.

Python Solution

1
2python
3class Solution:
4    def __init__(self):
5        self.visited = {}
6    
7    def copyRandomList(self, head):
8        if head is None:
9            return None
10        if head in self.visited:
11            return self.visited[head]
12        
13        node = Node(head.val, None, None)
14        self.visited[head] = node
15
16        node.next = self.copyRandomList(head.next)
17        node.random = self.copyRandomList(head.random)
18        
19        return node

JavaScript Solution

1
2javascript
3var Solution = function() {
4  this.visited = new Map();
5};
6
7Solution.prototype.copyRandomList = function(head) {
8  if (head === null) {
9    return null;
10  }
11  if (this.visited.has(head)) {
12    return this.visited.get(head);
13  }
14  
15  let node = new Node(head.val, null, null);
16  this.visited.set(head, node);
17
18  node.next = this.copyRandomList(head.next);
19  node.random = this.copyRandomList(head.random);
20  
21  return node;
22};

C# Solution

1
2csharp
3public class Solution {
4  Dictionary<Node, Node> visited = new Dictionary<Node, Node>();
5  
6  public Node CopyRandomList(Node head) {
7    if (head == null) {
8      return null;
9    }
10    if (this.visited.ContainsKey(head)) {
11      return this.visited[head];
12    }
13    
14    Node node = new Node(head.val);
15    this.visited[head] = node;
16
17    node.next = this.CopyRandomList(head.next);
18    node.random = this.CopyRandomList(head.random);
19    
20    return node;
21  }
22}

C++ Solution

1
2cpp
3class Solution {
4public:
5  unordered_map<Node*, Node*> map;
6
7  Node* copyRandomList(Node* head) {
8    if (head == nullptr)
9      return nullptr;
10    if (map.find(head) != map.end())
11      return map[head];
12
13    Node* newNode = new Node(head->val);
14    map[head] = newNode;
15    newNode->next = copyRandomList(head->next);
16    newNode->random = copyRandomList(head->random);
17    
18    return newNode;
19  }
20};

Java Solution

1
2java
3public class Solution {
4  HashMap<Node, Node> visited = new HashMap<>();
5  
6  public Node copyRandomList(Node head) {
7    if (head == null) {
8      return null;
9    }
10    if (this.visited.containsKey(head)) {
11      return this.visited.get(head);
12    }
13    
14    Node node = new Node(head.val);
15    this.visited.put(head, node);
16
17    node.next = this.copyRandomList(head.next);
18    node.random = this.copyRandomList(head.random);
19    
20    return node;
21  }
22}

That's the end of our article on how to create a deep copy of a linked list with random pointers. To summarize, we've learned how to solve this problem using a depth-first search (DFS) algorithm and a hash map. We've also learned how to implement this solution in Python, JavaScript, C#, C++, and Java.

We made use of a hash map to keep track of nodes that we have already visited and copied. We then iterated through the original Linked List using a DFS. While iterating through the list, we created a copy node for each node and mapped it within our hashmap. We did this until we visited all nodes, and afterwards set the next and random pointers of our copied nodes.

It's important to note that this solution has a time complexity of O(n) as we're visiting each node exactly once, and a space complexity of O(n), which is necessary to store the copy of the list.

Hopefully, this example has demonstrated how hash maps and recursions can be effectively used in certain problem-solving situations. Whether you're solving similar problems in interviews or implementing similar features in a program, the approach used here will serve you well.