DAY 103 - Copy List with Random Pointer

Hey Guys!, Welcome to DAY 103 and we are continuing on our journey to master linked list. Today we are back with an interesting question. So Let's get right down to it.

Question: Copy List with Random Pointer

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.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node. Your code will only be given the head of the original linked list.

Examples:

Example 1:

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

Example 2:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Question Breakdown:

• Ok so despite the lengthy the problem is quite easy to understand.
• The description is asking us to make an exact to exact copy of the given linked list.
• So what's the catch? The catch is that we have to create a copy of new node and allocate it in a new memory(space), we can't use the old linked list or have any of our nodes point back to it's nodes.
• To add to our difficulty, they have given us a random pointer which points to any node in the linked list.

Intuition:

• Ok so this seems easy, we can just do a loop and make new Nodes and pointers for every and move ahead?.
• Yeah but we also need to deal with random pointers pointing at nodes that have not existed yet or been created yet.
• Look in example 1:, if we make a copy of it line by line our 2nd node points to last node, but if we haven't reached last node how will create a pointer to it.
• Well How about we forget pointing at all and first make all the nodes. If we don't assign pointer to it? how will we move, well we can use a map to link old list and new list.
• Using a map we can link them and after we have created nodes , now any of our node's next or random pointer's will point to a node that actually exists in memory.

Approach:

1. First Pass: Creating New Nodes

   • We start by iterating through the original list using a temporary pointer, temp.
   • While traversing, we create a new node for each node in the original list and assign its val with the same value as the original node.
   • We also store a mapping between the original node and the new node in an unordered map (nodes) for the creation of random pointers later.

2. Second Pass: Setting next and random Pointers

   • We reset temp to the head of the original list.
   • While traversing the original list again, we set the next and random pointers for each new node.
   • For the next pointer, we look up the mapping in the nodes map to find the corresponding new node.
   • For the random pointer, we do the same: look up the mapping to find the corresponding new node.

3. Returning the Result

   • Finally, we return the head of the new list, which is stored in nodes[head].

Code:

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> nodes; //use to store link to old nodes and new nodes

        Node* temp = head; //temporary pointer to fill nodes

        while(temp){
            nodes[temp] = new Node(temp->val); //make copy of node and attach to nodes
            temp = temp->next;

        }
        temp = head; //reinitialize the pointer so that we can traverse again
        while(temp){
            Node* newNode = nodes[temp];
            newNode->next = nodes[temp->next];
            newNode->random = nodes[temp->random];
            temp = temp->next;
        }

        return nodes[head];
    }
};

Time and Space Complexity

Let's analyze the time and space complexity of this solution:

• Time Complexity: This solution makes two passes through the entire linked list. Therefore, the time complexity is O(N), where N is the number of nodes in the linked list.

• Space Complexity: The space complexity is O(N) as well. We use additional space to store the mapping between original nodes and new nodes in the nodes hash map. The space required for the new linked list is also O(N) as we create a new node for each node in the original list.