Copy Linked List with random pointer

Problem 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 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 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 map = new HashMap(); return copy(head,map); } public Node copy(Node node,Map 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; } }

Apr 18, 2025 - 17:15

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

}