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
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
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
Y in the original list, where
X.random --> Y, then for the corresponding two nodes
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
random_index: the index of the node (range from
n-1) that the
randompointer points to, or
nullif it does not point to any node.
Your code will only be given the
head of the original linked list.
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Input: head = [[1,1],[2,1]]
Iterative with O(1) Space
Instead of a separate dictionary to keep the old node → new node mapping, we can tweak the original linked list and keep every cloned node next to its original node. This interleaving of old and new nodes allows us to solve this problem without any extra space. Lets look at how the algorithm works.
- Traverse the original list and clone the nodes as you go and place the cloned copy next to its original node. This new linked list is essentially a interweaving of original and cloned nodes.
As you can see we just use the value of original node to create the cloned copy. The
next pointer is used to create the weaving. Note that this operation ends up modifying the original linked list.
cloned_node.next = original_node.next
original_node.next = cloned_node
2. Iterate the list having both the new and old nodes intertwined with each other and use the original nodes’ random pointers to assign references to random pointers for cloned nodes. For eg. If
B has a random pointer to
A, this means
B' has a random pointer to
3. Now that the
random pointers are assigned to the correct node, the
next pointers need to be correctly assigned to unweave the current linked list and get back the original list and the cloned list.
- Time Complexity : O(N)
- Space Complexity : O(1)