138. Copy List with Random Pointer

📝 Problem Details

• Title: 138. Copy List with Random Pointer
• Link: https://leetcode.com/problems/copy-list-with-random-pointer/
• Difficulty: Medium
• Tags/Categories: Linked-List Hashmap
• Neetcode Reference: Video Link

---

🔍 Problem Understanding

• we are given a linked list of nodes where each node has the following member variables:

int val;
Node* next;
Node* random;

• the random pointer can point to any node in the list or nullptr
• the task is to create a deep copy of the list such that:
  • every node in the copied list is brand new (not a reference to the old one)
  • the next and random pointers in the copied list match those in the original

---

🎯 Key Insights

Using a hashmap
	- we can use an unordered_map to map each original node to its corresponding copied node
	- this allows us to assign the next and random pointers in a second pass

---

⌛ Complexity Analysis

Time Complexity: O(n)
- single pass through to populate the map
- second pass through the construct the new list

Space Compelxity: O(n)
- use of hashmap 

---

💻 Implementation of Solution

/*
// 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<Node*, Node*> map;
 
        Node* curr = head;
        while(curr) {
            map[curr] = new Node(curr->val);
            curr = curr->next;
        }
 
        curr = head;
        while(curr) {
            map[curr]->next = map[curr->next];
            map[curr]->random = map[curr->random];
            curr = curr->next;
        }
 
        return map[head];
    }
};