138. Copy List with Random Pointer

Intuition

To deep copy a linked list with both next and random pointers, we need a strategy to maintain relationships between original nodes and their corresponding copied nodes while ensuring that each connection (both next and random) in the copied list points to nodes within the copied list itself.

Approach

1. HashMap for Mapping: Use a hashmap (visited) to efficiently map each original node to its copied counterpart. This allows us to quickly retrieve copied nodes and connect them appropriately.
2. Two-Pass Approach: - First Pass: Create a shallow copy of each node without connecting the random pointers. - Second Pass: Connect the next pointers and random pointers of each copied node using the mappings stored in the visited hashmap.
3. Implementation Steps: - Initialize an empty visited hashmap to store mappings from original nodes to their copied nodes. - Traverse the original linked list: - Create a new node for each original node, store it in visited, and set its val. - Traverse the original linked list again: - Connect the next pointers of each copied node using the visited hashmap. - Connect the random pointers of each copied node using the random_index provided in the original node's representation.

Complexity

Time Complexity:

O(N), where N is the number of nodes in the linked list. We perform two passes over the list, and each hashmap operation (insertion and retrieval) is average O(1).

Space Complexity:

O(N) due to the hashmap storing N nodes, plus the space required for the output linked list.

Code

C++

/*
// 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) {
        if (!head) return nullptr;
        
        unordered_map visited;
        
        // Function to recursively copy the linked list
        function copy = [&](Node* node) -> Node* {
            if (!node) return nullptr;
            if (visited.count(node)) return visited[node];
            
            Node* new_node = new Node(node->val);
            visited[node] = new_node;
            new_node->next = copy(node->next);
            new_node->random = copy(node->random);
            
            return new_node;
        };
        return copy(head);
    }
};

Python

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: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
        
        visited = {}
        
        # First pass: create copies of all nodes without connecting random pointers
        original = head
        while original:
            visited[original] = Node(original.val)
            original = original.next
        
        # Second pass: connect next and random pointers for copied nodes
        original = head
        while original:
            copied = visited[original]
            copied.next = visited.get(original.next)
            copied.random = visited.get(original.random)
            original = original.next
        
        return visited[head]

Java

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        // Map to store mapping from original nodes to their copies
        Map visited = new HashMap<>();

        // Function to recursively copy the linked list
        return copy(head, visited);
    }
    private Node copy(Node node, Map visited) {
        if (node == null) {
            return null;
        }

        // If the node has already been visited, return its copy
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // Create a new node with the same value
        Node newNode = new Node(node.val);

        // Store the mapping from the original node to its copy
        visited.put(node, newNode);

        // Recursively copy the next and random pointers
        newNode.next = copy(node.next, visited);
        newNode.random = copy(node.random, visited);

        return newNode;
    }
}

JavaScript

/**
 * // 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) {
    const visited = new Map();

    const copy = (node) => {
        if (!node) return null;
        if (visited.has(node)) return visited.get(node);

        const newNode = new Node(node.val);
        visited.set(node, newNode);

        newNode.next = copy(node.next);
        newNode.random = copy(node.random);

        return newNode;
    };
    return copy(head);
};