Copy List with Random Pointer
Problem Description
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 <= 104
Node.randomisnullor is pointing to some node in the linked list.
Solve it on LeetCode
Approaches
1. HashMap
Intuition:
The main idea is to traverse the original linked list and copy each node. During this traversal, a HashMap is used to keep track of the original nodes and their corresponding copied nodes. By using this map, we can access the copied node of a particular original node efficiently.
The algorithm can be summarized in two main passes over the linked list:
- Copy Nodes and Fill HashMap:
- Create a new list node for each node in the original list,
- Save the mapping between the original node and copied node in a
HashMap. - Assign Next and Random Pointers:
- Iterate over the original list again. For each node, set the
nextandrandompointers for the copied nodes using the HashMap.
Code:
- Time Complexity: O(N), where N is the number of nodes in the linked list. We iterate over the list twice.
- Space Complexity: O(N), as we store N node mappings in the HashMap.
2. Interleaved List
Intuition:
We can optimize the space used for storing node mappings by integrating the copied nodes directly into the original list. The procedure is as follows:
- First pass: For each node in the original list, create a new node and interleaved it between the current node and the next node.
- Second pass: Assign
randompointers for the newly created nodes by utilizing the existingrandompointers. - Third pass: Separate the original and copied list.
This approach removes the need for a HashMap to store node mappings, thereby reducing the space complexity.
Code:
- Time Complexity: O(N), where N is the number of nodes in the linked list. We iterate over the list twice.
- Space Complexity: O(N), as we store N node mappings in the HashMap.