Back to Linked List
Medium
Copy List with Random Pointer
A linked list of length `n` is given such that each node contains an additional random pointer, which could point to any node in the list, or `null`. Construct a deep copy of the list.
Examples
Input:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output:[[7,null],[13,0],[11,4],[10,2],[1,0]]
Input:head = [[1,1],[2,1]]
Output:[[1,1],[2,1]]
Constraints
0 <= n <= 1000-10^4 <= Node.val <= 10^4Node.random is null or is pointing to some node in the linked list.
Approach
Use a hash map to map original nodes to their newly created deep copies. In the first pass, iterate through the original list and create a new node for each original node, storing the mapping `old_node -> new_node` in the hash map. In the second pass, iterate through the original list again. For each node, use the hash map to set the `next` and `random` pointers of its corresponding new node.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
This is the most intuitive approach, using extra space for the hash map.
Solution.java
/*// 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) { if (head == null) return null; Map<Node, Node> oldToNew = new HashMap<>(); // First pass: create all copy nodes Node curr = head; while (curr != null) { oldToNew.put(curr, new Node(curr.val)); curr = curr.next; } // Second pass: wire next and random pointers curr = head; while (curr != null) { Node copy = oldToNew.get(curr); copy.next = oldToNew.get(curr.next); copy.random = oldToNew.get(curr.random); curr = curr.next; } return oldToNew.get(head); }}