### 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.

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

## Comments

## Post a Comment