Leetcode 138: Copy List with Random Pointer

Input: A linked list of nodes, each containing two pointers: a next pointer and a random pointer, which can point to any node or be null.

Example: head = [[5,null],[10,0],[15,4],[20,2],[25,1]]

Constraints:

• 0 <= n <= 1000

• -10^4 <= Node.val <= 10^4

• Node.random is null or points to some node in the linked list.

Output: Return the head of the deep copied linked list, where the copied list has the same values, next pointers, and random pointers as the original list.

Example: Output: [[5,null],[10,0],[15,4],[20,2],[25,1]]

Constraints:

• The copied list should have no shared nodes with the original list.

Goal: Create a deep copy of the linked list by ensuring that both the next and random pointers of the new nodes represent the same list structure as the original list.

Steps:

• 1. Iterate through the original list and create new nodes for each node in the original list.

• 2. Set the next pointer of each new node to match the corresponding next pointer in the original list.

• 3. Set the random pointer of each new node to match the corresponding random pointer in the original list.

• 4. Use a map or hash table to store mappings between the original nodes and their corresponding new nodes to handle random pointers efficiently.

Goal: The constraints ensure that the solution can handle linked lists with up to 1000 nodes while maintaining the correct structure for random pointers.

Steps:

• 0 <= n <= 1000

• -10^4 <= Node.val <= 10^4

• Node.random is null or points to some node in the linked list.

Assumptions:

• The input list contains nodes with valid random pointers that either point to a valid node or are null.

• Input: head = [[5,null],[10,0],[15,4],[20,2],[25,1]]

• Explanation: The original list contains five nodes with random pointers. The deep copy should have the same structure, where the next and random pointers of the new nodes match the original list.

• Input: head = [[1,1],[2,1]]

• Explanation: This example contains a two-node list where both nodes have random pointers pointing to each other. The deep copy should replicate the same structure.

Approach: To solve this problem, we will create a deep copy of the list by iterating through the original list and using a map to maintain references to the new nodes.

Observations:

• We need to handle the random pointers, which require mapping original nodes to new nodes to ensure the correct structure.

• We will use a hash map to store the relationship between the original nodes and the copied nodes, allowing us to efficiently update the random pointers.

Steps:

• 1. Initialize a hash map to store the mapping of original nodes to new nodes.

• 2. Traverse the original list and create new nodes, saving the new node in the map.

• 3. Set the next and random pointers for each new node using the map.

Empty Inputs:

• If the input list is empty (null head), return null.

Large Inputs:

• The solution should handle lists with up to 1000 nodes efficiently.

Special Values:

• If a node's random pointer is null, the corresponding new node's random pointer should also be null.

Constraints:

• The solution should maintain a linear time complexity and constant space for the mapping.

map<Node*, Node*> mp;
Node* copyRandomList(Node* head) {
    mp.clear();
    return copy(head);
    
}

Node* copy(Node* head) {
    if(!head) return head;
    if(mp.count(head)) return mp[head];
    
    Node* node = new Node(head->val);
    mp[head] = node;
    node->next = copy(head->next);
    node->random = copy(head->random);
    
    return node;
}

1 : Variable Declaration

map<Node*, Node*> mp;

A map `mp` is declared to store the mapping between the original node and the newly copied node.

2 : Function Definition (copyRandomList)

Node* copyRandomList(Node* head) {

This is the definition of the `copyRandomList` function, which will clone the entire list starting from the given head node.

3 : Clear Map

    mp.clear();

The map `mp` is cleared to ensure that no previous data remains before starting the copy process.

4 : Recursive Call (copyRandomList)

    return copy(head);

The `copyRandomList` function calls the helper function `copy`, passing the head node to begin the cloning process.

5 : Helper Function Definition (copy)

Node* copy(Node* head) {

This is the definition of the helper function `copy`, which handles the actual node cloning process for each individual node.

6 : Base Case (null)

    if(!head) return head;

If the input `head` is null, return null. This is the base case of the recursion.

7 : Check if Node is Already Copied

    if(mp.count(head)) return mp[head];

If the node has already been copied (i.e., it exists in the map `mp`), return the corresponding copied node.

8 : Node Creation

    Node* node = new Node(head->val);

A new node is created with the same value as the original node.

9 : Store Copy in Map

    mp[head] = node;

The newly created node is stored in the map `mp`, with the original node as the key.

10 : Recursive Copy (Next Pointer)

    node->next = copy(head->next);

Recursively copy the `next` pointer of the current node by calling `copy` on the next node.

11 : Recursive Copy (Random Pointer)

    node->random = copy(head->random);

Recursively copy the `random` pointer of the current node by calling `copy` on the random node.

12 : End Function (copy)

    return node;

Return the newly created and fully cloned node.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) as we need to traverse the entire linked list once.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) due to the map used to store the original-to-new node mapping.

Leetcode 138: Copy List with Random Pointer

Solution to LeetCode 138: Copy List with Random Pointer Problem

Explore →