1138. Copy List with Random Pointer 🚀

---

Solution Developed In:

The Question

For this article we will be covering Leetcode's '138. Copy List with Random Pointer' question. Which is a very similar problem to the 133. Clone Graph question.

Question:

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Explaining The Question

This Question is rated Medium. Which I believe is entirely accurate, so long as you have solid foundations in understanding Linked Lists, Pointers, and Recursion. Ideally you should know what a Depth First Search is, and how to use it to solve this problem.

In this solution I will be using a Depth First Search to solve this problem.

What we're being asked is to clone a Linked List that has a random pointer on each node. Now while that may sound easy to clone a linked list and it's random pointers, it's not as easy as it sounds. Because we need to ensure that when creating the random pointers new node that it inst duplicated. Meaning it's a reference to a new or already existing node.

The real challenge here is the prevention of duplicate nodes.

---

Recommended Knowledge

1. Linked Lists
2. Depth First Search (Recursive)
3. Hash Map

What do we know?

1. We're given the head of a linked list.
2. We need to copy the each node and it's random pointers node.
3. We need to ensure we're not creating duplicate nodes, meaning that the random pointer could reference a node we have already created and thus we need to point towards the already existing node and not create a new one.

How we're going to do it:

We're going to recursively create this Linked Liss. The way we're going to do this is by using conducting a Depth First Search on the Linked List, at each node we visit we will create our own node (root) that is a copy of said node, and we will then add the old node to a hashmap (visited_nodes) to keep track of the nodes we've already visited. So we can prevent the duplication of nodes. Sometimes this is called Memoization.

At each node that we have not seen in the visited_nodes before we create it, we then conduct the same DFS on the random of that node, which will return us a reference to the node we need to point towards, either newly created or from visited_nodes.

1. We're going to firstly create a visited_nodes hashmap to keep track of all of our visited nodes
2. We will then perform a Depth First Search (create_list) on all the nodes in the input linked list, and we will create a new node for each node in the input list.
3. In this Depth First Search we firstly ask 'Have we been to this node before?' if we have we will return the node that we have already created, if we have not we will create a new node and add it to the visited_nodes hashmap. This will make sense in just a second
4. So at this point, we have not visited this node, so we create it, and then we conduct a Depth First Search on the random of this node, which may mean we need to create that random node, or we may already have created it, so we ask our hashmap if we have seen this node before, if we have we will return the node that we have already created, if we have not we will create a new node and add it to the visited_nodes hashmap.
5. Once the Depth First Search has been conducted on all the nodes of the list, we return the root node (Head of linked list).

Big O Notation:

• Time Complexity: O(n) | Where n is the number of nodes in the Linked List. As we will need to traverse the entire linked list.
• Space Complexity: O(n) | Where n is the number of nodes in the Linked List as we will be storing a refernce of each node inside of a hashmap.

It is technically possible to complete this solution in O(1) space, but the solution is complex and I wouldn't recommend you learn it either, as learning this pattern shown is more useful than learning the O(1) space solution. As the pattern of Memoization and Depth First Search is seen almost everywhere, especially in technical interviews.

Leetcode Results:

See Submission Link:

• Runtime: 78 ms, faster than 61.15% of JavaScript online submissions for Copy List with Random Pointer
• Memory Usage: 43.9 MB, less than 68.43% of JavaScript online submissions for Copy List with Random Pointer.

---

The Solution

var copyRandomList = function (head) {
    // So this will store the node's we've already created
    // we'll use this to prevent us from creating the same node twice.
    // Old node -> copied new node
    const visited_nodes = new Map();

    // We're going to recursively create the list
    // by creating a new node for each old node.
    // And populating that node with a recursive call to our function using the old node's neighbors, next / random
    // Each time we do this, we add the new node to the hashmap, so we can always return the same node for the same old node.
    const create_list = (head) => {
        // Empty head given,
        // return null. This will happen at the end of a list
        if (!head) {
            return null;
        }

        // We have already visited this node before,
        // so return the node we already created as to prevent a double creation.
        if (visited_nodes.has(head)) {
            return visited_nodes.get(head);
        }

        // Create that new node, and index it to indicate we have visited it.
        const root = new Node(head.val);
        visited_nodes.set(head, root);

        // Let's get the random node to this new node.
        // We do this by recursively calling our function on the old node's random node.
        // Each time we do this, we add the new node to the hashmap, so we can always return the same node for the same old node.
        root.random = create_list(head.random);
        root.next   = create_list(head.next);

        // Because of backtracking, we always return the partially created list
        // to it's caller and so on and so on. Until we get back to the orignally caller
        // being the linked list head which will be returned.
        return root;
    };

    return create_list(head);
};