Leetcode - 138. Copy List with Random Pointer

Copy List with Random Pointer – JavaScript Approach

Problem Statement

You are given a linked list where each node contains an additional random pointer that can point to any node in the list or be null. Your task is to create a deep copy of this list.

---

Approach

To solve this problem efficiently, we will use Hashing (Map-based solution). The approach consists of two main steps:

Step 1: Create a mapping of original nodes to their clones

• Traverse the original list and create a copy of each node.
• Store each original node as a key and its cloned node as a value in a Map.

Step 2: Assign the next and random pointers for cloned nodes

• Iterate through the original list again.
• Use the Map to assign next and random pointers correctly.

---

Code Implementation

/**
 * // 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;

    let map = new Map();

    // Step 1: Create a copy of all nodes and store them in the map
    let curr = head;
    while (curr) {
        map.set(curr, new Node(curr.val, null, null));
        curr = curr.next;
    }

    // Step 2: Assign next and random pointers
    curr = head;
    while (curr) {
        map.get(curr).next = map.get(curr.next) || null;
        map.get(curr).random = map.get(curr.random) || null;
        curr = curr.next;
    }

    return map.get(head);
};

---

Complexity Analysis

• Time Complexity: (O(N))

  • We traverse the linked list twice: once to create copies and once to update pointers. Both operations take linear time.

• Space Complexity: (O(N))

  • We use a HashMap to store original nodes and their copies, which requires additional space proportional to the number of nodes.

---

Alternative Approach (O(1) Space Complexity)

Instead of using extra space, we can modify the linked list structure temporarily:

1. Interweave the cloned nodes with the original list
   • Example: Original list: A -> B -> C, transform it into A -> A' -> B -> B' -> C -> C'.
2. Assign the random pointers correctly
   • Each cloned node’s random pointer is set as originalNode.random.next.
3. Separate the original and cloned list
   • Restore the original list and extract the copied list.

This method reduces space complexity to (O(1)), but it modifies the original list temporarily.

---

Conclusion

The HashMap approach provides a clean and intuitive way to solve the problem. If space optimization is needed, the interweaving method is preferable. This problem is commonly asked in coding interviews, making it a great practice question for linked list manipulation. 🚀