Solution For Copy List With Random Pointer

Problem description:

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.

Example:
Input:
{“$id”:”1″,”next”:{“$id”:”2″,”next”:null,”random”:{“$ref”:”2″},”val”:2},”random”:{“$ref”:”2″},”val”:1}
Explanation:
Node 1’s value is 1, both of its next and random pointer points to Node 2.
Node 2’s value is 2, its next pointer points to null and its random pointer points to itself.

Solution:

The given linked list contains random pointers, which means that each node can point to any node in the list. To create a deep copy of this linked list, we need to copy each node and its random pointer.

To solve this problem, we can use a hash table to store the created nodes. We iterate through the input linked list and create a new node for each node encountered. We add the new node to the hash table. Then we copy the next and random pointers of the original node to the new node. If the next or random pointer of the original node is null, we assign it to null. If the next or random pointer of the original node points to a node that has not been created yet, we create the node and add it to the hash table. If the next or random pointer of the original node points to a node that has already been created, we use the corresponding node in the hash table.

At the end of the iteration, we return the head of the deep copy linked list.

Code:

/
* Definition for a Node.
* function Node(val,next,random) {
* this.val = val;
* this.next = next;
* this.random = random;
* };
*/
/
* @param {Node} head
* @return {Node}
*/
var copyRandomList = function(head) {
if (!head) {
return null;
}
const map = new Map();
let curr = head;
while (curr) {
const newNode = new Node(curr.val, null, null);
map.set(curr, newNode);
curr = curr.next;
}
curr = head;
while (curr) {
const newNode = map.get(curr);
newNode.next = map.get(curr.next) || null;
newNode.random = map.get(curr.random) || null;
curr = curr.next;
}
return map.get(head);
};

Explanation:

In the above solution, we first check for the base case when the head is null. Then we create an empty hash table to store the created nodes. We initialize the current node to the head of the input linked list.

We then iterate through the input linked list and create a new node for each node encountered. We add the new node to the hash table using the original node as the key. Then we move to the next node in the input linked list.

Next, we iterate through the input linked list again and copy the next and random pointers of each node to the corresponding new node. We check whether the next or random pointer of the original node is null or not. If it is not null, we check whether the next or random node has already been created or not. If it has not been created, we create a new node and add it to the hash table. If it has been created, we use the corresponding node in the hash table.

Finally, we return the head of the deep copy linked list, which is the node corresponding to the head of the input linked list in the hash table.

Step by Step Implementation For Copy List With Random Pointer

/**
 * // Definition for a Node.
 * class Node {
 *     int val;
 *     Node next;
 *     Node random;
 *     Node() {}
 *     Node(int val) { this.val = val; }
 *     Node(int val, Node next, Node random) {
 *         this.val = val;
 *         this.next = next;
 *         this.random = random;
 *     }
 * }
 */

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        
        // create copies of each node and link them together in a new list
        Node curr = head;
        while (curr != null) {
            Node copy = new Node(curr.val);
            copy.next = curr.next;
            curr.next = copy;
            curr = copy.next;
        }
        
        // set random pointers for each node in new list
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }
        
        // split new list from old list
        curr = head;
        Node copyHead = head.next;
        while (curr != null) {
            Node temp = curr.next;
            curr.next = temp.next;
            if (temp.next != null) temp.next = temp.next.next;
            curr = curr.next;
        }
        return copyHead;
    }
}

# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        # if head is None, return None
        if not head:
            return None
        
        # create a dictionary to store the old nodes as keys and new nodes as values
        nodes_dict = dict()
        
        # create a new node with the same value as head
        new_head = Node(head.val)
        
        # set the key as head and value as new_head in the dictionary
        nodes_dict[head] = new_head
        
        # set head to head.next (move to the next node in the list)
        head = head.next
        
        # create a new node to keep track of the new list
        new_node = new_head
        
        # iterate through the list until head is None
        while head:
            # create a new node with the same value as head
            new_node.next = Node(head.val)
            
            # set the key as head and the value as new_node.next in the dictionary
            nodes_dict[head] = new_node.next
            
            # set head to head.next (move to the next node in the list)
            head = head.next
            
            # set new_node to new_node.next (move to the next node in the new list)
            new_node = new_node.next
        
        # set head back to the head of the original list
        head = new_head
        
        # iterate through the new list until head is None
        while head:
            # if the current node has a random node
            if head.random:
                # set the current node's random node to the node in the dictionary with the same value as the current node's random node
                head.random = nodes_dict[head.random]
            
            # set head to head.next (move to the next node in the list)
            head = head.next
        
        # return the new head
        return new_head

/**
 * // Definition for a Node.
 * function Node(val,next,random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */
/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
    
    // Edge case - if head is null, return null
    if(head === null) {
        return null;
    }
    
    // Create a map to store old nodes as keys and new nodes as values
    let map = new Map();
    
    // Create a new head
    let newHead = new Node(head.val);
    
    // Set the head of the map to be the old head and the new head
    map.set(head, newHead);
    
    // Set pointers for the new head
    let oldCurr = head;
    let newCurr = newHead;
    
    // Iterate through the list
    while(oldCurr.next) {
        
        // Set next for the new node
        newCurr.next = new Node(oldCurr.next.val);
        
        // Set random for the new node if it exists
        if(oldCurr.random) {
            newCurr.random = new Node(oldCurr.random.val);
        }
        
        // Set the key of the old node's next to be the old node's next
        map.set(oldCurr.next, newCurr.next);
        
        // Move old and new pointers
        oldCurr = oldCurr.next;
        newCurr = newCurr.next;
    }
    
    // Set random for the last new node if it exists
    if(oldCurr.random) {
        newCurr.random = new Node(oldCurr.random.val);
    }
    
    // Iterate through the map
    for(let [oldNode, newNode] of map) {
        
        // Set random for each new node using the map
        if(oldNode.random) {
            newNode.random = map.get(oldNode.random);
        }
    }
    
    // Return the new head
    return newHead;
};

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(head == NULL) return NULL;
        RandomListNode *node = head;
        //copy next pointers
        while(node!=NULL){
            RandomListNode *temp = new RandomListNode(node->label);
            temp->next = node->next;
            node->next = temp;
            node = node->next->next;
        }
        node = head;
        //copy random pointers
        while(node!=NULL){
            if(node->random != NULL)
                node->next->random = node->random->next;
            node = node->next->next;
        }
        node = head;
        RandomListNode *copy = head->next;
        //restore next pointers
        while(node != NULL){
            RandomListNode *temp = node->next;
            node->next = temp->next;
            if(temp->next != NULL) temp->next = temp->next->next;
            node = node->next;
        }
        return copy;
    }
};

/**
 * Definition for a Node.
 * public class Node {
 *     public int val;
 *     public Node next;
 *     public Node random;
 *     public Node(int _val) {
 *         val = _val;
 *         next = null;
 *         random = null;
 *     }
 * }
 */
public class Solution {
    public Node CopyRandomList(Node head) {
        // Create a dictionary to store old nodes as keys and new nodes as values
        Dictionary map = new Dictionary();
        
        // Iterate through the old list, creating new nodes along the way and storing them in the map
        Node curr = head;
        while (curr != null) {
            map.Add(curr, new Node(curr.val));
            curr = curr.next;
        }
        
        // Reset curr to the head of the old list
        curr = head;
        
        // Iterate through the old list again, this time assigning next and random pointers for each new node
        while (curr != null) {
            map[curr].next = map.ContainsKey(curr.next) ? map[curr.next] : null;
            map[curr].random = map.ContainsKey(curr.random) ? map[curr.random] : null;
            curr = curr.next;
        }
        
        // Return the head of the new list
        return map.ContainsKey(head) ? map[head] : null;
    }
}