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: Interweave the cloned nodes with the original list Example: Original list: A -> B -> C, transform it into A -> A' -> B -> B' -> C -> C'. Assign the random pointers correctly Each cloned node’s random pointer is set as originalNode.random.next. 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.

Mar 24, 2025 - 08:36

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:

Interweave the cloned nodes with the original list
- Example: Original list: A -> B -> C, transform it into A -> A' -> B -> B' -> C -> C'.
Assign the random pointers correctly
- Each cloned node’s random pointer is set as originalNode.random.next.
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.