Copy List with Random Pointer
Deep-copy a linked list where each node has a next pointer and a random pointer. No node in the copy may refer to an original node.
Work through the cases
3 examplesInput notation
Values on line 1; matching random-pointer indices on line 2. Use -1 for null. Next pointers follow input order.Expected result
The copied values on line 1 and copied random indices on line 2. Verify in your code that nodes are newly allocated.Case 1
Input
7 4 9 2 -1 0
Expected output
7 4 9 2 -1 0
Case 2
Input
5 0
Expected output
5 0
Case 3
Input
3 3 -1 0
Expected output
3 3 -1 0
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Copy a list whose random pointer may refer to any node or null. If we copy next first, the random target may not exist yet. n ≤ 1000. A first pass builds the new list along next and maps each original node to its copy; a second pass wires random through that map.
We can define a dummy head node dummy and use a pointer tail to point to the dummy head node. Then, we traverse the linked list, copying each node and storing the mapping between each node and its copy in a hash table d, while also connecting the next pointers of the copied nodes.
Next, we traverse the linked list again and use the mappings stored in the hash table to connect the random pointers of the copied nodes.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the linked list.
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
Map<Node, Node> d = new HashMap<>();
Node dummy = new Node(0);
Node tail = dummy;
for (Node cur = head; cur != null; cur = cur.next) {
Node node = new Node(cur.val);
tail.next = node;
tail = node;
d.put(cur, node);
}
for (Node cur = head; cur != null; cur = cur.next) {
d.get(cur).random = cur.random == null ? null : d.get(cur.random);
}
return dummy.next;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.