138. Copy List with Random Pointer

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:

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.
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.
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:

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.
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.
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.

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.
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:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know

138. Copy List with Random Pointer

Problem Description

Intuition

Solution Approach

Step 1: Interleaving the Original and Copied Nodes

Step 2: Setting the random Pointers for Copied Nodes

Step 3: Separating the Copied List from the Original List

Ready to land your dream job?

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

Example Walkthrough

Step 1: Interleaving the Original and Copied Nodes

Step 2: Setting the random Pointers for Copied Nodes

Step 3: Separating the Copied List from the Original List

Solution Implementation

Time and Space Complexity

Time Complexity:

Space Complexity:

Recommended Readings

Step 2: Setting the `random` Pointers for Copied Nodes

Step 2: Setting the `random` Pointers for Copied Nodes