### 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:
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 {
if(head == null) return null; //if null can't clone
HashMap<Node, Node> map = new 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;
}
}
}
```

Other Posts You May Like