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:

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.

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.

1Original List:
21 -> 2 -> 3 -> null
3|    |    |
4v    v    v
52   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.

1After interleaving:
21 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
3|           |           |
4v           v           v
52          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.

1Interleaved list with `random` pointers set:
21 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
3|     |     |     |     |     |
4v     v     v     v     v     v
52    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.

1Restored original list:
21 -> 2 -> 3 -> null
3|    |    |
4v    v    v
52   null  1
6
7Separated copied list (deep copy):
81' -> 2' -> 3' -> null
9|      |      |
10v      v      v
112'    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

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.