tc :O(n) where n is no. of nodes in the original linked list
Iterative approach:
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
HashMap<Node,Node> map = new HashMap<>();
Node node = new Node(0);
Node temp = node;
while(head!=null){
Node duplicateNode = get(map,head);
temp.next = duplicateNode;
Node duplicateRandomNode = get(map, head.random);
duplicateNode.random = duplicateRandomNode;
temp = temp.next;
head = head.next;
}
return node.next;
}
public Node get(Map<Node,Node> map, Node node){
if(node ==null) return null;
if(map.containsKey(node)) return map.get(node);
map.put(node, new Node(node.val));
return map.get(node);
}
}
Recursive approach:
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
Map<Node,Node> map = new HashMap<>();
return copy(head,map);
}
public Node copy(Node node,Map<Node,Node> map){
if(node == null) return null;
if(map.containsKey(node)) return map.get(node);
map.put(node, new Node(node.val));
Node duplicate = map.get(node);
duplicate.next = copy(node.next,map);
duplicate.random = copy(node.random,map);
return duplicate;
}
}