Clone a linked list with next and random pointer

Clone a linked list with next and random pointer

  April 25, 2020    

---

Problem : 

You are given a Singly Linked List with N nodes where each node next pointing to its next node and its random pointer pointing to some random node in linked list.

We need to create a clone of it.

Solution :

Here we can take O(N) space approach where we can create a clone of all the nodes and store them in correspondence to original nodes in a hashMap. By this we got to know that which cloned node is created for which original node.

After that , we can connect all the pointers(next and random) by iterating it again.

Code :

HashMap<Node,Node> createClone(Node head) {
        HashMap<Node,Node> hash = new HashMap<>();
        Node cur = head;
        while(cur!=null) {
            Node newNode = new Node(cur.data);
            hash.put(cur, newNode);
            cur = cur.next;
        }
        return hash;
    }

    void connectNodes(HashMap<Node,Node> hash, Node head) {
        Node cur = head;
        while(cur!=null) {
            Node clonedNode = hash.get(cur);
            clonedNode.next = hash.get(cur.next);
            clonedNode.arb = hash.get(cur.arb);
            cur = cur.next;
        }
    }

 //main method to create copy
    Node copyList(Node head) {
        HashMap<Node,Node> hash = createClone(head);
        connectNodes(hash,head);
        return hash.get(head);
    }