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:
Copy a Linked List with Random Pointer - The Coding Shala
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
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to Create a Simple Calculator - The Coding Shala

N-th Tribonacci Number Solution - The Coding Shala

Java Program to Convert Binary to Decimal - The Coding Shala

LeetCode - Shuffle the Array Solution - The Coding Shala

Introduction to Kotlin Programming Language for Backend Development - The Coding Shala