Copy a Linked List with Random Pointer - The Coding Shala

Home >> Interview Questions >> copy a linked list with random pointer

Copy a Linked List with Random Pointer

In this post, you will learn how to copy or clone a linked list with random pointer and its solution in Java. 

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list not the reference of the original node.

Example:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Copy a Linked List with Random Pointer Java Solution

Approach 1:

Using HashMap - extra Space O(n). We can store all node as key and make new node as value. In the next loop can assign next and random pointer to the copied nodes.

Java Program: 

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null; //if null can't clone
        Node curr = head;
        HashMap<Node, Node> map = new HashMap<>();
        //add to the hashmap
        while(curr != null){
            map.put(curr, new Node(curr.val)); //making new node as value;
            curr = curr.next;
        }
        curr = head;
        //link next and random to the nodes
        while(curr != null){
            map.get(curr).next = map.get(curr.next);
            map.get(curr).random = map.get(curr.random);
            curr = curr.next;
        }
        //return original head from map
        return map.get(head);
    }
}

Other Posts You May Like

• Flatten a multilevel doubly linked list
• Rotate a linked list
• Merge two sorted linked list
• Add two numbers represented as a linked list
• Check if given linked list is palindrome or not

Please leave a comment below if you like this post or found some error, it will help me to improve my content.