# Copy List with Random Pointer **Difficulty:** MEDIUM [External](https://leetcode.com/problems/copy-list-with-random-pointer) Canonical: https://scaleengineer.com/dsa/problems/copy-list-with-random-pointer **Data structures:** Hash Table, Linked List **Companies:** [Docusign](https://scaleengineer.com/companies/docusign), [Flipkart](https://scaleengineer.com/companies/flipkart), [Google](https://scaleengineer.com/companies/google), [Intel](https://scaleengineer.com/companies/intel), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Snowflake](https://scaleengineer.com/companies/snowflake), [Uber](https://scaleengineer.com/companies/uber), [VMware](https://scaleengineer.com/companies/vmware), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [eBay](https://scaleengineer.com/companies/ebay), [PhonePe](https://scaleengineer.com/companies/phonepe), [oyo](https://scaleengineer.com/companies/oyo), [Mobileye](https://scaleengineer.com/companies/mobileye) --- ## Problem 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**](https://en.wikipedia.org/wiki/Object%5Fcopying#Deep%5Fcopy) of the list. The deep copy should consist of exactly `n` **brand new** nodes, where each new node has its value set to the value of its corresponding original node. Both the `next` and `random` pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. **None of the pointers in the new list should point to nodes in the original list**. For example, if there are two nodes `X` and `Y` in the original list, where `X.random --> Y`, then for the corresponding two nodes `x` and `y` in the copied list, `x.random --> y`. Return _the head of the copied linked list_. The linked list is represented in the input/output as a list of `n` nodes. Each node is represented as a pair of `[val, random_index]` where: * `val`: an integer representing `Node.val` * `random_index`: the index of the node (range from `0` to `n-1`) that the `random` pointer points to, or `null` if it does not point to any node. Your code will **only** be given the `head` of the original linked list. **Example 1:** ![](https://assets.glich.co/dsa/copy-list-with-random-pointer/image0.png) **Input:** head = [[7,null],[13,0],[11,4],[10,2],[1,0]] **Output:** [[7,null],[13,0],[11,4],[10,2],[1,0]] **Example 2:** ![](https://assets.glich.co/dsa/copy-list-with-random-pointer/image1.png) **Input:** head = [[1,1],[2,1]] **Output:** [[1,1],[2,1]] **Example 3:** **![](https://assets.glich.co/dsa/copy-list-with-random-pointer/image2.png)** **Input:** head = [[3,null],[3,0],[3,null]] **Output:** [[3,null],[3,0],[3,null]] **Constraints:** * `0 <= n <= 1000` * `-104 <= Node.val <= 104` * `Node.random` is `null` or is pointing to some node in the linked list. # Approaches ## Recursive Cloning with a Hash Map This approach uses recursion to traverse the original list and build the new list. A hash map is used to store the mapping between original nodes and their newly created copies. This map is essential for two reasons: it prevents re-creating a node that has already been copied, and it correctly handles cycles formed by the `random` pointers, preventing infinite recursion. **Time:** O(N) · **Space:** O(N) **Pros:** Conceptually simple and follows the recursive definition of a linked list.; The code is concise and elegant. **Cons:** Can lead to a `StackOverflowError` if the linked list is very long, as the recursion depth can be up to N.; The space complexity includes the recursion stack, which can be significant in addition to the hash map. ### Explanation The core idea is a recursive function that takes a node from the original list and returns its corresponding copy in the new list. We use a `HashMap` to act as a memoization table or a "visited" set. The key is a node from the original list, and the value is its copy. **Algorithm Steps**: 1. If the input `node` is `null`, we've reached the end of a chain, so we return `null`. 2. Before doing anything else, we check if the `node` is already in our hash map. If it is, it means we've already started processing this node (likely due to a `random` pointer), so we just return its copy from the map. 3. If the `node` is not in the map, we create a new `Node` with the same value. 4. Crucially, we immediately put the `original_node` -> `new_node` mapping into the hash map. This must be done *before* the recursive calls to handle cycles correctly. 5. Then, we recursively call the function to build the rest of the list: - The `next` pointer of our new node is set by calling the function on `original_node.next`. - The `random` pointer is set by calling the function on `original_node.random`. 6. Finally, we return the newly created node. ```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 { // HashMap to store the mapping from original node to its copy. private HashMap visited = new HashMap<>(); public Node copyRandomList(Node head) { if (head == null) { return null; } // If we have already processed the current node, simply return the cloned version. if (this.visited.containsKey(head)) { return this.visited.get(head); } // Create a new node with the same value as the old node. Node node = new Node(head.val); // Save this value in the hash map. This is needed before the recursive calls // to prevent infinite loops in case of cycles. this.visited.put(head, node); // Recursively copy the remaining linked list starting from the next pointer and random pointer. node.next = this.copyRandomList(head.next); node.random = this.copyRandomList(head.random); return node; } } ``` ### Algorithm - Create a global `HashMap` to store mappings from original nodes to copied nodes. - Define a recursive function `copy(node)`: - Base case: If `node` is `null`, return `null`. - Memoization: If `node` is in the hash map, return the mapped value. - Create a new `Node` called `newNode` with `node.val`. - Add the mapping `(node, newNode)` to the hash map. This must be done before the recursive calls to handle cycles. - Set `newNode.next = copy(node.next)`. - Set `newNode.random = copy(node.random)`. - Return `newNode`. - Call `copy(head)` to start the process. ## Iterative Cloning with a Hash Map This approach is an iterative counterpart to the recursive solution. It uses a hash map to associate original nodes with their copies, but it avoids recursion, making it more robust against stack overflow issues. The process is typically done in two passes: the first pass creates all the new nodes and maps them to the original nodes, and the second pass sets the `next` and `random` pointers for the new nodes. **Time:** O(N) · **Space:** O(N) **Pros:** Avoids recursion, so there's no risk of stack overflow, making it more robust for large inputs.; The logic is straightforward with two distinct passes for node creation and pointer connection. **Cons:** Requires O(N) extra space for the hash map, which might be a concern for memory-constrained environments. ### Explanation This method systematically clones the list without using the call stack, which makes it safer for very large inputs. **Algorithm Steps**: 1. Handle the edge case where the input `head` is `null`. If so, return `null`. 2. Create a `HashMap` to store the mapping from an original node to its copy. 3. **First Pass: Clone Nodes and Values.** - Initialize a pointer `ptr` to the `head` of the original list. - Iterate through the original list. For each node `ptr` points to, create a new `Node` with the same value. - Store this `original_node` -> `new_node` pair in the hash map. - Move to the next node: `ptr = ptr.next`. 4. **Second Pass: Connect Pointers.** - Reset the pointer `ptr` back to the `head` of the original list. - Iterate through the original list again. For each node `ptr`: - Find its copy in the map: `copied_node = map.get(ptr)`. - The `next` pointer of the copied node should point to the copy of the original node's `next` node. We can find this copy in the map: `copied_node.next = map.get(ptr.next)`. - Similarly, set the `random` pointer: `copied_node.random = map.get(ptr.random)`. - Move to the next node: `ptr = ptr.next`. 5. Return the head of the new list, which is `map.get(head)`. ```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; } HashMap map = new HashMap<>(); // First pass: create all nodes and put them in the map. Node curr = head; while (curr != null) { map.put(curr, new Node(curr.val)); curr = curr.next; } // Second pass: assign next and random pointers. curr = head; while (curr != null) { Node copiedNode = map.get(curr); copiedNode.next = map.get(curr.next); copiedNode.random = map.get(curr.random); curr = curr.next; } return map.get(head); } } ``` ### Algorithm - If `head` is `null`, return `null`. - Create a `HashMap`. - **Pass 1**: Iterate through the original list. For each node, create a new `Node` with the same value and store the mapping `(original_node, new_node)` in the hash map. - **Pass 2**: Iterate through the original list again. For each `original_node`: - Get its copy: `copied_node = map.get(original_node)`. - Set `copied_node.next = map.get(original_node.next)`. - Set `copied_node.random = map.get(original_node.random)`. - Return `map.get(head)`. ## Iterative with O(1) Space (Interweaving Nodes) This is a highly optimized approach that cleverly avoids the need for a hash map, thus reducing the space complexity to O(1) (excluding the space for the new list itself). It works by temporarily modifying the original list's structure. The new, copied nodes are "interwoven" with the original nodes. This creates a direct, accessible link from an original node to its copy, which allows for setting the `random` pointers without an auxiliary data structure. **Time:** O(N) · **Space:** O(1) **Pros:** Extremely space-efficient, using only O(1) extra space.; It's an in-place algorithm (though it temporarily modifies the list structure). **Cons:** The logic is more complex than the hash map approach.; It modifies the original list, which might be undesirable in some contexts (though it restores it in the end). ### Explanation This method is performed in three main passes. **Algorithm Steps**: 1. **First Pass: Create and Interweave Copied Nodes.** - Iterate through the original list. For each node, create a new `Node` with the same value and insert it immediately after the original node. After this pass, the list will look like `A -> A' -> B -> B' -> ...`, where `A'` is the copy of `A`. 2. **Second Pass: Assign Random Pointers.** - Iterate through the interwoven list. For each original node `ptr`, its copy is `ptr.next`. The `random` pointer of the copy (`ptr.next.random`) should point to the copy of the original's random target (`ptr.random`). Since the copy of any node `X` is `X.next`, the copy of `ptr.random` is `ptr.random.next`. So, we set `ptr.next.random = (ptr.random != null) ? ptr.random.next : null;`. 3. **Third Pass: Separate the Lists.** - The final step is to "unzip" the interwoven list into two separate lists: the original and the copied one. This involves carefully rewiring the `next` pointers to restore the original list and form the new list. ```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; } // Pass 1: Create a copy of each node and interleave them. // A -> A' -> B -> B' -> ... Node ptr = head; while (ptr != null) { Node newNode = new Node(ptr.val); newNode.next = ptr.next; ptr.next = newNode; ptr = newNode.next; } // Pass 2: Assign random pointers for the copied nodes. ptr = head; while (ptr != null) { if (ptr.random != null) { ptr.next.random = ptr.random.next; } ptr = ptr.next.next; } // Pass 3: Separate the interwoven list into original and copied lists. Node oldListPtr = head; Node newListPtr = head.next; Node newListHead = head.next; while (oldListPtr != null) { oldListPtr.next = oldListPtr.next.next; newListPtr.next = (newListPtr.next != null) ? newListPtr.next.next : null; oldListPtr = oldListPtr.next; newListPtr = newListPtr.next; } return newListHead; } } ``` ### Algorithm - **Pass 1**: Iterate through the original list. For each node, create a copy and insert it between the current node and its `next` node. - **Pass 2**: Iterate through the modified list. For each original node `curr`, set its copy's random pointer: `curr.next.random = curr.random.next`. Handle the `null` case for `curr.random`. - **Pass 3**: Iterate through the modified list again to separate the two lists. Restore the `next` pointers of the original list and link the `next` pointers of the copied list. - Return the head of the copied list. # Solutions ### CSharp ```csharp /* // Definition for a Node. public class Node { public int val; public Node next; public Node random; public Node(int _val) { val = _val; next = null; random = null; } } */ public class Solution { public Node CopyRandomList ( Node head ) { if ( head == null ) { return null ; } for ( Node cur = head ; cur != null ; ) { Node node = new Node ( cur . val , cur . next ); cur . next = node ; cur = node . next ; } for ( Node cur = head ; cur != null ; cur = cur . next . next ) { if ( cur . random != null ) { cur . next . random = cur . random . next ; } } Node ans = head . next ; for ( Node cur = head ; cur != null ; ) { Node nxt = cur . next ; if ( nxt != null ) { cur . next = nxt . next ; } cur = nxt ; } return ans ; } } ``` ### Java ```java public class Copy_List_with_Random_Pointer { /** * Definition for singly-linked list with a random pointer. * class RandomListNode { * int label; * RandomListNode next, random; * RandomListNode(int x) { this.label = x; } * }; */ /* 1. 在原链表的每个节点后面拷贝出一个新的节点。 2. 依次给新的节点的随机指针赋值，而且这个赋值非常容易 cur->next->random = cur->random->next。 3. 断开链表可得到深度拷贝后的新链表。 */ public class Solution_noExtraMap { public RandomListNode copyRandomList ( RandomListNode head ) { if ( head == null ) { return null ; } // duplicate new node right after RandomListNode current = head ; while ( current != null ) { RandomListNode t = new RandomListNode ( current . label ); t . next = current . next ; current . next = t ; current = t . next ; } // random pointer update for duplicate new node current = head ; while ( current != null ) { if ( current . random != null ) { current . next . random = current . random . next ; } current = current . next . next ; } // cut copied list out current = head ; RandomListNode res = head . next ; while ( current != null ) { RandomListNode t = current . next ; current . next = t . next ; if ( t . next != null ) { t . next = t . next . next ; } current = current . next ; } return res ; } } public class Solution { // map from original node, to its copy node HashMap < RandomListNode , RandomListNode > hm = new HashMap <>(); public RandomListNode copyRandomList ( RandomListNode head ) { if ( head == null ) { return null ; } RandomListNode current = head ; while ( current != null ) { RandomListNode currentCopy = getNodeCopy ( current ); RandomListNode currentNextCopy = getNodeCopy ( current . next ); RandomListNode currentRandomCopy = getNodeCopy ( current . random ); currentCopy . next = currentNextCopy ; currentCopy . random = currentRandomCopy ; current = current . next ; } return hm . get ( head ); } private RandomListNode getNodeCopy ( RandomListNode originalNode ) { if ( originalNode == null ) { // @note: missed this check, last node will cause error, whose next is null return null ; } if ( hm . containsKey ( originalNode )) { return hm . get ( originalNode ); } else { RandomListNode nodeCopy = new RandomListNode ( originalNode . label ); hm . put ( originalNode , nodeCopy ); return nodeCopy ; } } } } ############ /* // 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 ; } for ( Node cur = head ; cur != null ;) { Node node = new Node ( cur . val , cur . next ); cur . next = node ; cur = node . next ; } for ( Node cur = head ; cur != null ; cur = cur . next . next ) { if ( cur . random != null ) { cur . next . random = cur . random . next ; } } Node ans = head . next ; for ( Node cur = head ; cur != null ;) { Node nxt = cur . next ; if ( nxt != null ) { cur . next = nxt . next ; } cur = nxt ; } return ans ; } } ``` ### JavaScript ```javascript /** * // Definition for a Node. * function Node(val, next, random) { * this.val = val; * this.next = next; * this.random = random; * }; */ /** * @param {Node} head * @return {Node} */ var copyRandomList = function (head) { if (!head) { return null; } for (let cur = head; cur; ) { const node = new Node(cur.val, cur.next, null); cur.next = node; cur = node.next; } for (let cur = head; cur; cur = cur.next.next) { if (cur.random) { cur.next.random = cur.random.next; } } const ans = head.next; for (let cur = head; cur; ) { const nxt = cur.next; if (nxt) { cur.next = nxt.next; } cur = nxt; } return ans; }; ``` ### Python ```python # Definition for singly-linked list with a random pointer. # class RandomListNode(object): # def __init__(self, x): # self.label = x # self.next = None # self.random = None class Solution : def copyRandomList ( self , head : "Node" ) -> "Node" : if head is None : return None cur = head while cur : # copy nodes node = Node ( cur . val , cur . next ) cur . next = node cur = node . next cur = head while cur : # copy random pointers if cur . random : cur . next . random = cur . random . next cur = cur . next . next ans = head . next cur = head while cur : # cut into 2 lists nxt = cur . next if nxt : cur . next = nxt . next cur = nxt return ans class Solution : # with a map def copyRandomList ( self , head : 'Node' ) -> 'Node' : if not head : return None node_map = {} # Create the copy nodes without next and random connections current = head while current : node_map [ current ] = Node ( current . val ) current = current . next # Assign next and random connections for the copy nodes current = head while current : copy_node = node_map [ current ] copy_node . next = node_map . get ( current . next ) copy_node . random = node_map . get ( current . random ) current = current . next return node_map [ head ] ``` ### CPP ```cpp // OJ: https://leetcode.com/problems/copy-list-with-random-pointer/ // Time: O(N) // Space: O(1) class Solution { public: Node * copyRandomList ( Node * head ) { auto p = head ; while ( p ) { auto node = p ; p = p -> next ; auto copy = new Node ( node -> val ); node -> next = copy ; copy -> next = p ; } p = head ; while ( p ) { if ( p -> random ) p -> next -> random = p -> random -> next ; p = p -> next -> next ; } p = head ; Node h ( 0 ), * tail = & h ; while ( p ) { auto node = p -> next ; p -> next = node -> next ; p = p -> next ; tail -> next = node ; tail = node ; } return h . next ; } }; ```