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

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.