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'snext
is now its copy. This makes it easy to find and set the copied node'srandom
pointer: iforiginalNode.random
exists, thencopiedNode.random
will beoriginalNode.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 thenext
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 thatcur.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 iscur.next
. - The random node of
cur
iscur.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
tocur.next
, which is the copied node following the originalcur
node. - Re-assign
cur.next
tonxt.next
, which is the next original node in the list (ornull
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 (ornull
), usingcur = 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 EvaluatorExample 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
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, whereN
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.
How does quick sort divide the problem into subproblems?
Recommended Readings
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
LeetCode 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 we
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 algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.