Facebook Pixel

138. Copy List with Random Pointer

MediumHash TableLinked List
Leetcode Link

Problem Description

The problem provides a special type of linked list where each node has two pointers: a next pointer to the next node in the sequence and a random pointer that can point to any node in the list or be null. The task is to create a deep copy of this linked list. A deep copy means that you need to create a new list where each node in the new list corresponds to a node in the original list, but no pointers in the new list should reference nodes from the original list. The newly created list should maintain the original structure, including the next and random linkages. The input is the head of the original linked list, and the output should be the head of the newly copied linked list.

Intuition

To solve this problem, we need to create a copy of each node and also map the random pointers from the original list to the corresponding nodes in the copied list. This can become complex because the random pointer can point to any node, creating a non-linear structure.

The solution follows these steps:

  1. Iterate through the original list and create a copy of each node, insert the copied node directly after its original node. This links the original and the copied nodes in a single mixed list.

  2. Go through the mixed list again and set the random pointers for the copied nodes. Since we've interleaved the copied nodes with their corresponding originals, each original node's next is now its copy. This makes it easy to find and set the copied node's random pointer: if originalNode.random exists, then copiedNode.random will be originalNode.random.next.

  3. Finally, we need to restore the original list and separate the copied list from it. We iterate through the mixed list, re-establish the original next links for the original nodes, and create the next links for the copied nodes.

Following this approach ensures that we create a deep copy of the list without needing extra space for a map to track the random pointer relationships which is a common approach for such problems.

Learn more about Linked List patterns.

Solution Approach

The solution for creating a deep copy of the linked list with a random pointer is implemented in three major steps:

Step 1: Interleaving the Original and Copied Nodes

We start by iterating through the original list. For each node in the list, we perform the following actions:

  • Create a new node with the same value as the current node (cur.val).
  • Insert this new node right after the current one by setting the next pointer of the new node to point to the node that cur.next was originally pointing to.
  • Update cur.next to point to the newly created node.
  • Move forward in the list by setting cur to the next original node (cur = cur.next.next).

This step essentially weaves the original and new nodes together.

Step 2: Setting the random Pointers for Copied Nodes

In the second pass over this interleaved list, we set the random pointer for each copied node. If the random pointer of the original node is not null, we can find the corresponding random pointer for the copied node as follows:

  • Given an original node cur, its copied node is cur.next.
  • The random node of cur is cur.random.
  • Therefore, the corresponding copied random node would be cur.random.next.

We set this with cur.next.random = cur.random.next.

Step 3: Separating the Copied List from the Original List

Finally, we restore the original list to its initial state and extract the deep copy. We iterate over the interleaved list and do the following actions:

  • Set nxt to cur.next, which is the copied node following the original cur node.
  • Re-assign cur.next to nxt.next, which is the next original node in the list (or null if we are at the end).
  • Then, we update cur to point to the copied node's next node, which should also be a copied node (or null), using cur = nxt.
  • Continue this process until all nodes have been visited.

By the end of step 3, we will have the original list restored and a separately linked new list, which is a deep copy of the original list.

This approach is efficient as it does not require extra space for maintaining a hash table to map the original to copied nodes, and it completes the copying in linear time.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the following linked list where the next pointers form a simple sequence and the random pointers point to various nodes, including null.

Original List:
1 -> 2 -> 3 -> null
|    |    |
v    v    v
2   null  1

Node 1 has a random pointer to Node 2, Node 2's random pointer is null, and Node 3's random pointer points back to Node 1.

Step 1: Interleaving the Original and Copied Nodes

We create a copy of each node and interleave it with the original list.

After interleaving:
1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
|           |           |
v           v           v
2          null         1

Here, 1', 2', and 3' are the copied nodes of 1, 2, and 3 respectively. Each original node's next pointer now points to its newly created copy.

Step 2: Setting the random Pointers for Copied Nodes

Now, we set up the random pointers for the copied nodes.

Interleaved list with `random` pointers set:
1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
|     |     |     |     |     |
v     v     v     v     v     v
2    2'   null   null   1    1'

Copied node 1''s random pointer goes to 2', 2''s random pointer remains null, and copied node 3''s random pointer goes to 1'.

Step 3: Separating the Copied List from the Original List

Finally, we untangle the two lists into the original list and its deep copy.

Restored original list:
1 -> 2 -> 3 -> null
|    |    |
v    v    v
2   null  1

Separated copied list (deep copy):
1' -> 2' -> 3' -> null
|      |      |
v      v      v
2'    null    1'

We're left with two separate lists: the original list is unchanged, and we have a new deep copy list which maintains the original structure, including the random links.

This process creates a deep copy of a complex linked list with random pointers in O(n) time and O(1) additional space.

Solution Implementation

1class Node:
2    def __init__(self, val: int, next: 'Node' = None, random: 'Node' = None):
3        self.val = val
4        self.next = next
5        self.random = random
6
7class Solution:
8    def copyRandomList(self, head: 'Node') -> 'Node':
9        # If the original list is empty, return None.
10        if not head:
11            return None
12      
13        # Step 1: Create new nodes weaved within the original list
14        current = head
15        while current:
16            # cloned_node is a copy of the current node without the random reference
17            cloned_node = Node(current.val, current.next)
18            current.next = cloned_node       # Insert the cloned node just after the current node
19            current = cloned_node.next       # Move to the next original node
20      
21        # Step 2: Assign random pointers to the cloned nodes
22        current = head
23        while current:
24            if current.random:
25                # Set the cloned node's random to the cloned node of the original node's random
26                current.next.random = current.random.next
27            current = current.next.next       # Move two steps forward
28      
29        # Step 3: Detach the original and cloned list from each other
30        original_current = head
31        cloned_head = head.next
32        while original_current:
33            cloned_current = original_current.next
34            original_current.next = cloned_current.next  # Fix the original list's next pointer
35            # Fix the cloned list's next pointer, only if cloned_current has a next node
36            if cloned_current.next:
37                cloned_current.next = cloned_current.next.next
38            # Move to the next original node
39            original_current = original_current.next
40      
41        # Return the head of the cloned linked list
42        return cloned_head
43
1class Solution {
2    public Node copyRandomList(Node head) {
3        // Return null if the original list is empty
4        if (head == null) {
5            return null;
6        }
7
8        // 1. Create a cloned node for each node in the original list and insert it 
9        // right next to the original node.
10        for (Node current = head; current != null; ) {
11            Node clone = new Node(current.val); // Clone node
12            clone.next = current.next; // Set clone's next to current node's next
13            current.next = clone; // Insert cloned node after the current node
14            current = clone.next; // Move to the next original node
15        }
16
17        // 2. Assign random pointers for the cloned nodes.
18        for (Node current = head; current != null; current = current.next.next) {
19            if (current.random != null) {
20                // Set the cloned node's random to the cloned node of the original node's random
21                current.next.random = current.random.next;
22            }
23        }
24
25        // 3. Restore the original list and extract the cloned list.
26        Node copyHead = head.next; // Head of the cloned list
27        for (Node current = head; current != null; ) {
28            Node clone = current.next; // The cloned node
29            // Restore the original list's 'next' pointers
30            current.next = clone.next;
31            // Set the cloned node's 'next' pointers. Check if the next original node exists.
32            clone.next = (clone.next != null) ? clone.next.next : null;
33            // Move to the next original node
34            current = current.next;
35        }
36      
37        // Return the head of the cloned list
38        return copyHead;
39    }
40}
41
42// Definition for a Node.
43class Node {
44    public int val; // Value of the node
45    public Node next; // Reference to the next node in the list
46    public Node random; // Reference to a random node in the list
47
48    public Node(int val) {
49        this.val = val;
50        this.next = null;
51        this.random = null;
52    }
53}
54
1/*
2// Definition for a Node.
3class Node {
4public:
5    int val;
6    Node* next;
7    Node* random;
8
9    Node(int _val) {
10        val = _val;
11        next = NULL;
12        random = NULL;
13    }
14};
15*/
16class Solution {
17public:
18    Node* copyRandomList(Node* head) {
19        if (!head) {
20            return nullptr; // If the input list is empty, return nullptr.
21        }
22
23        // First pass: Create a new node for each existing node and interleave them.
24        for (Node* current = head; current != nullptr;) {
25            Node* newNode = new Node(current->val);
26            newNode->next = current->next;
27            current->next = newNode;
28            current = newNode->next;
29        }
30
31        // Second pass: Assign random pointers for the new nodes.
32        for (Node* current = head; current != nullptr; current = current->next->next) {
33            if (current->random != nullptr) {
34                current->next->random = current->random->next;
35            }
36        }
37
38        // Third pass: Separate the original list from the copied list and prepare the return value.
39        Node* copiedListHead = head->next;
40        for (Node* current = head; current != nullptr;) {
41            Node* copiedNode = current->next;
42            // Advance the current pointer in the original list to the next original node
43            current->next = copiedNode->next;
44            // Advance the copiedNode pointer in the copied list to the next copied node, 
45            // if it exists
46            if (copiedNode->next != nullptr) {
47                copiedNode->next = copiedNode->next->next;
48            }
49            // Move to the next original node
50            current = current->next;
51        }
52
53        // Return the head of the copied list.
54        return copiedListHead;
55    }
56};
57
1// Definition for Node that represents each node in a linked list.
2interface Node {
3  val: number;
4  next: Node | null;
5  random: Node | null;
6}
7
8/**
9 * Creates a deep copy of a linked list where each node has a random pointer.
10 *
11 * @param {Node | null} head - The head of the linked list to be copied.
12 * @return {Node | null} The head of the copied linked list.
13 */
14function copyRandomList(head: Node | null): Node | null {
15    // Initialize a map to keep track of already copied nodes.
16    const clonedNodesMap = new Map<Node, Node>();
17
18    // First pass: copy all the nodes and map the original nodes to their copies.
19    let currentNode = head;
20    while (currentNode !== null) {
21        clonedNodesMap.set(currentNode, { val: currentNode.val, next: null, random: null });
22        currentNode = currentNode.next;
23    }
24
25    // Second pass: Assign the next and random pointers.
26    currentNode = head;
27    while (currentNode !== null) {
28        // Set the next pointer of the cloned node.
29        clonedNodesMap.get(currentNode)!.next = currentNode.next ? clonedNodesMap.get(currentNode.next) : null;
30        // Set the random pointer of the cloned node.
31        clonedNodesMap.get(currentNode)!.random = currentNode.random ? clonedNodesMap.get(currentNode.random) : null;
32        // Move to the next original node.
33        currentNode = currentNode.next;
34    }
35
36    // Return the cloned head which is the copy of the original head.
37    return head ? clonedNodesMap.get(head) : null;
38}
39

Time and Space Complexity

The given code implements a method to copy a linked list with a next and a random pointer.

Time Complexity:

The algorithm involves three main steps:

  1. Iterating through the original list and creating a copy of each node which is inserted between the original node and its next node: This step takes O(N) time, where N is the number of nodes in the list.

  2. Iterating through the list again to update the random pointers of the copied nodes: For each of the original nodes, the corresponding copied node's random pointer is updated to the copied random node. This step also takes O(N) time.

  3. Finally, the copied nodes are separated from the original list to form the copied list: As we iterate through the list to reconstruct the original and copied lists, this step also takes O(N) time.

Since all steps are performed sequentially, the overall time complexity is O(N) + O(N) + O(N), which simplifies to O(N).

Space Complexity:

The space complexity consists of the additional space required by the algorithm excluding the input and output.

  1. The copied nodes are created in between the original nodes, so there is no need for extra space for maintaining relationships or indexes which would otherwise be the case if a hash table were used. Therefore, no extra space proportional to the number of elements in the list is used.

  2. The space used by the nodes themselves is not considered in the space complexity analysis as it is part of the output.

Thus, the space complexity is O(1) as we're only using a constant amount of extra space, regardless of the input size (ignoring the space required for the output).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More