**Problem**

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

space complexity?*O*(*1*)

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
`next`

pointers. 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.

**Complexity Analysis**

**Implementation**

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;};`