### Given a Linked List with random pointers, can you do a deep copy of the list?

The idea is to use a `HashMap` to store the nodes. The key will be the current node and the value will be our new node. If the current node has random node, then we set the random node for our new node as well. Let's see the solution:

``````    public Node copyRandomList(Node head) {

}

Map<Node, Node> map = new HashMap<>();
Node dummy = new Node(0);
Node pre = dummy;
Node newNode = null;

} else{
newNode = new Node(head.val);
}
pre.next = newNode;

} else{
newNode.random = new Node(head.random.val);
}
}
pre = newNode;
}
return dummy.next;
}
``````

Using hash map will allocate `O(n)` space, but can we do it without allocating new space?

The second solution (without hash map) works like this:

1. transform list `1->2->3-4` into `1->1'->2->2'->3->3'->4->4'`
2. copy random node, ex: `1ʳᵃⁿᵈ->5` to `1ʳᵃⁿᵈ'->5'`
3. modify list to return the new copied list only

Here's the solution:

``````    public Node copyRandomList(Node head) {
}

Node node = head;

// 1. copy node and add in between current and next node
while(node != null){
Node newNode = new Node(node.val);
newNode.random = node.random;
newNode.next = node.next;
node.next = newNode;
node = node.next.next;
}

// reset to head

// 2. copy random node
while(node != null){
if(node.random != null){
node.next.random = node.random.next;
}
node = node.next.next;
}

Node dummy = new Node(0);
Node prev = dummy;
// reset to head

// 3. split the list into original and copied list
while(node != null){
Node newNode = node.next;
node.next = newNode.next;
prev.next = newNode;
prev = newNode;
node = node.next;
}

return dummy.next;
}
``````

Here's visual graph for understanding:   Note | If your newly allocated space is not your input or output, then you are not allocating new extra space.

That's all! Thanks for reading!

Post was published on , last updated on .

Like the content? Support the author by paypal.me!