Copy List with Random Pointer
MedPrompt
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. 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 representingNode.valrandom_index: the index of the node (range from0ton-1) that therandompointer points to, ornullif it does not point to any node.
Your code will only be given the head of the original linked list.
Example 1:
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:
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]Example 3:
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
Constraints:
0 <= n <= 1000-104 <= Node.val <= 104Node.randomisnullor is pointing to some node in the linked list.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Create a global
HashMap<Node, Node>to store mappings from original nodes to copied nodes. - Define a recursive function
copy(node):- Base case: If
nodeisnull, returnnull. - Memoization: If
nodeis in the hash map, return the mapped value. - Create a new
NodecallednewNodewithnode.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.
- Base case: If
- Call
copy(head)to start the process.
Walkthrough
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<Node, Node> 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:
- If the input
nodeisnull, we've reached the end of a chain, so we returnnull. - Before doing anything else, we check if the
nodeis already in our hash map. If it is, it means we've already started processing this node (likely due to arandompointer), so we just return its copy from the map. - If the
nodeis not in the map, we create a newNodewith the same value. - Crucially, we immediately put the
original_node->new_nodemapping into the hash map. This must be done before the recursive calls to handle cycles correctly. - Then, we recursively call the function to build the rest of the list:
- The
nextpointer of our new node is set by calling the function onoriginal_node.next. - The
randompointer is set by calling the function onoriginal_node.random.
- The
- Finally, we return the newly created node.
/*// 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<Node, Node> 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; }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
Pros
Conceptually simple and follows the recursive definition of a linked list.
The code is concise and elegant.
Cons
Can lead to a
StackOverflowErrorif 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.
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.
Algorithm
- If
headisnull, returnnull. - Create a
HashMap<Node, Node>. - Pass 1: Iterate through the original list. For each node, create a new
Nodewith 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).
- Get its copy:
- Return
map.get(head).
Walkthrough
This method systematically clones the list without using the call stack, which makes it safer for very large inputs.
Algorithm Steps:
- Handle the edge case where the input
headisnull. If so, returnnull. - Create a
HashMap<Node, Node>to store the mapping from an original node to its copy. - First Pass: Clone Nodes and Values.
- Initialize a pointer
ptrto theheadof the original list. - Iterate through the original list. For each node
ptrpoints to, create a newNodewith the same value. - Store this
original_node->new_nodepair in the hash map. - Move to the next node:
ptr = ptr.next.
- Initialize a pointer
- Second Pass: Connect Pointers.
- Reset the pointer
ptrback to theheadof 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
nextpointer of the copied node should point to the copy of the original node'snextnode. We can find this copy in the map:copied_node.next = map.get(ptr.next). - Similarly, set the
randompointer:copied_node.random = map.get(ptr.random).
- Find its copy in the map:
- Move to the next node:
ptr = ptr.next.
- Reset the pointer
- Return the head of the new list, which is
map.get(head).
/*// 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<Node, Node> 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); }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
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.
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.
Algorithm
- Pass 1: Iterate through the original list. For each node, create a copy and insert it between the current node and its
nextnode. - 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 thenullcase forcurr.random. - Pass 3: Iterate through the modified list again to separate the two lists. Restore the
nextpointers of the original list and link thenextpointers of the copied list. - Return the head of the copied list.
Walkthrough
This method is performed in three main passes.
Algorithm Steps:
-
First Pass: Create and Interweave Copied Nodes.
- Iterate through the original list. For each node, create a new
Nodewith the same value and insert it immediately after the original node. After this pass, the list will look likeA -> A' -> B -> B' -> ..., whereA'is the copy ofA.
- Iterate through the original list. For each node, create a new
-
Second Pass: Assign Random Pointers.
- Iterate through the interwoven list. For each original node
ptr, its copy isptr.next. Therandompointer of the copy (ptr.next.random) should point to the copy of the original's random target (ptr.random). Since the copy of any nodeXisX.next, the copy ofptr.randomisptr.random.next. So, we setptr.next.random = (ptr.random != null) ? ptr.random.next : null;.
- Iterate through the interwoven list. For each original node
-
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
nextpointers to restore the original list and form the new list.
- The final step is to "unzip" the interwoven list into two separate lists: the original and the copied one. This involves carefully rewiring the
/*// 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; }}Complexity
Time
O(N)
Space
O(1)
Trade-offs
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).
Solutions
Solution
/* // 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 ; } }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 ; } }/** * // 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; };# 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 ]// 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 ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.