Copy List with Random Pointer medium

Problem Statement

A linked list of length n is given such that each node contains an integer val and a pointer to the next node in the list. The given head points to the beginning node of this list.

You must build a deep copy of the given linked list, including both the values in each node and pointers in the list structure. The deep copy should have the same values and structure as the original list, but be entirely separate from the original. Each node in the deep copy must contain a copy of the val of its corresponding node in the original list, as well as the next and random pointers pointing to the corresponding nodes in the deep copy.

Note:

• The linked list can have cycles.
• You must return the head node of the newly created deep copy list.

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]] Explanation:

The input is a linked list containing 5 nodes. The integer values are [7, 13, 11, 10, 1]. The random pointers point to the nodes with the integer values as indicated. The output is a deep copy of this list, where the new nodes have the same values and random pointer relationships.

Example 2

Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]] Explanation: The input list has a cycle. The deep copy must also have the same cycle structure.

Steps

1. Create a mapping: We'll use a unordered_map to store a mapping between nodes in the original list and their corresponding nodes in the copied list. This allows us to easily find the copied node when we need to set the random pointer.

2. Iterate and copy: Iterate through the original list. For each node:

   • Create a new node with the same val.
   • Store the mapping between the original node and the new node in the unordered_map.
   • Set the next pointer of the newly created node.

3. Set random pointers: Iterate through the original list again. For each node, use the mapping to find the corresponding copied node and set its random pointer to the copied version of the random pointer from the original node.

4. Return the head of the copied list: Return the first node of the copied list.

Explanation

The key to solving this problem efficiently is using a hash map (unordered_map in C++) to avoid repeated searches and to maintain the correspondence between nodes in the original and copied lists. The iterative approach ensures we process each node exactly twice, resulting in linear time complexity. The space complexity is also linear due to the hash map.

Code (C++)

#include <iostream>
#include <unordered_map>

struct Node {
    int val;
    Node *next;
    Node *random;
    Node(int x) : val(x), next(nullptr), random(nullptr) {}
};

Node* copyRandomList(Node* head) {
    if (head == nullptr) return nullptr;

    unordered_map<Node*, Node*> visited; // Map original node to copied node

    Node* oldNode = head;
    Node* newNode = new Node(oldNode->val); // Create the first node copy
    visited[oldNode] = newNode; // Store the mapping

    while (oldNode != nullptr) {
        //copy next pointer
        if(oldNode->next != nullptr){
            if(visited.find(oldNode->next) == visited.end()){
                visited[oldNode->next] = new Node(oldNode->next->val);
            }
            newNode->next = visited[oldNode->next];
        }


        //copy random pointer
        if(oldNode->random != nullptr){
            if(visited.find(oldNode->random) == visited.end()){
                visited[oldNode->random] = new Node(oldNode->random->val);
            }
            newNode->random = visited[oldNode->random];
        }

        oldNode = oldNode->next;
        newNode = newNode->next;
    }

    return visited[head];
}

int main() {
  // Example usage (you can adapt this to test other inputs)
  Node* head = new Node(7);
  head->next = new Node(13);
  head->next->next = new Node(11);
  head->next->next->next = new Node(10);
  head->next->next->next->next = new Node(1);
  head->random = head->next->next->next->next;
  head->next->random = head;
  head->next->next->random = head->next->next->next->next;
  head->next->next->next->random = head->next->next;
  head->next->next->next->next->random = head;

  Node* copiedHead = copyRandomList(head);

  // Print the copied list (You would need a function to properly print the list's structure)
  // ... (Add code here to print the copied list)

  return 0;
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the list. We iterate through the list twice.
• Space Complexity: O(N). The unordered_map uses O(N) space in the worst case to store the mapping between original and copied nodes.