VietMX Staff asked 3 years ago
Every node of the linked list has a random pointer (in addition to the next pointer) which could randomly point to another node or be null. How would you duplicate such a Linked List? Could you do that in O(1) space complexity?
Let’s assume you have
public class Node { private Node next; private Node random; private String data; // getters and setters omitted for the sake of brevity}An intuitive solution is to keep a hash table for each node in the list, via which we just need to iterate the list in 2 rounds (2N steps) respectively to create nodes and assign the values for their random pointers. As a result, the space complexity of this solution is O(N), although with a linear time complexity.
- Walk the old list following the
nextpointers. For each node you visit, add a node to your new list, connect the previous node in your new list to the new node, store the old node random pointer in the new new node, then store a mapping of the old node pointer to the new node pointer in a map. - Walk the new list, and for each random pointer, look it up in the map to find the associated node in the new list to replace it with.
As an optimised solution, we could reduce the space complexity into constant. The idea is to associate the original node with its copy node in a single linked list. In this way, we don’t need extra space to keep track of the new nodes.
The algorithm is composed of the follow three steps which are also 3 iteration rounds.
- Iterate the original list and duplicate each node. The duplicate of each node follows its original immediately.
- Iterate the new list and assign the random pointer for each duplicated node.
- Restore the original list and extract the duplicated nodes.
Hash table version:
let deep_copy_arbitrary_pointer = function(head) { if (!head) { return null; } let current = head; let new_head = null; let new_prev = null; let ht = new Map(); // create copy of the linked list, recording the corresponding // nodes in hashmap without updating arbitrary pointer while (current) { let new_node = new LinkedListNode(current.data); // copy the old arbitrary pointer in the new node new_node.arbitrary = current.arbitrary; if (new_prev) { new_prev.next = new_node; } else { new_head = new_node; } ht.set(current, new_node); new_prev = new_node; current = current.next; } let new_current = new_head; // updating arbitrary pointer while (new_current) { if (new_current.arbitrary) { let node = ht.get(new_current.arbitrary); new_current.arbitrary = node; } new_current = new_current.next; } return new_head;};