How to Clone a Linked List with Next and Random Pointers in Java?

Today we'll see how to clone a linked list with next and random pointers in Java using simple approach.

The problem statement is - "You are given a linked list with two pointers. One pointer will point to the next node and the other pointer will be pointing to the random node i.e any node of the linked list. We have to write a program in O(n) time to clone or duplicate the list"

There are many ways to clone the linked list. But we will use the following method to clone a linked list -

1. We will traverse the linked list and make a copy of data of each node.
2. We will store the Original linked list node as key and Cloned linked list node as value into a HashMap.
3. We will traverse the Original linked list again, and using the HashMap assign the next and random pointers to the cloned linked list.

Now we will look into to program -

package com.anjan.clone;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// Node Class
class Node{
int data;
Node next, randPointer;

public Node(int data){
this.data = data;
this.next = null;
this.randPointer = null;
}
}

// Custom Linked List Class
class MyLinkedList{

private static Node head = null;

// Private Constructor for Cloning
private MyLinkedList(Node head){
this.head = head;
}

// Public Constructor
public MyLinkedList(){

}

// Inserting Data in Last
public void push(int data){
Node node = null;

if(head == null){
head = new Node(data);

}else{
node= new Node(data);
node.next = null;
Node temp = head;
while(temp.next != null){
temp = temp.next;
}
temp.next = node;
}
}

// Return Head Address
public Node getHead(){
return head;
}

// Method to display elements of Linked List
public void display(){

Node temp = head;

while(temp != null){
System.out.print("Data : "+temp.data+", Node Address : "+temp+", Next Data : ");
if(temp.next != null)
System.out.print(temp.next.data);
else
System.out.print(temp.next);

System.out.print(", Random Data : ");

if(temp.randPointer!= null)
System.out.print(temp.randPointer.data);
else
System.out.print(temp.randPointer);
temp = temp.next;
System.out.println("");
}

}

// Method to get Random Numbers between a Range
private int getRandom(int min, int max){
return (min + (int)(Math.random() * max));
}

// Method to set Random pointers
public void setRandomPointer(){
Node temp = getHead();

List<Node> list = new ArrayList<Node>();

while(temp != null){
list.add(temp);
temp = temp.next;
}

temp = getHead();

while(temp != null){
int n = getRandom(0, list.size()-1);
temp.randPointer = list.get(n);
list.remove(n);
temp = temp.next;
}
}

// Method to clone Linked List
public MyLinkedList clone(){

Node origCur = getHead();
Node cloneCur = null;

Map<Node, Node> map = new HashMap<Node, Node>();

while(origCur != null){
cloneCur = new Node(origCur.data);
map.put(origCur , cloneCur);
origCur = origCur.next;
}

origCur = getHead();

while(origCur != null){
cloneCur = map.get(origCur);
cloneCur.next = map.get(origCur.next);
cloneCur.randPointer = map.get(origCur.randPointer);
origCur = origCur.next;
}
return new MyLinkedList(map.get(getHead()));
}
}

public class CloneLinkedList {

public static void main(String args[]){
System.out.println("** Original Linked List **");
MyLinkedList origList = new MyLinkedList();
origList.push(1);
origList.push(2);
origList.push(3);
origList.push(4);
origList.push(5);
origList.setRandomPointer();
origList.display();

System.out.println("** Cloned Linked List **");
MyLinkedList cloneList = origList.clone();
cloneList.display();

}

}

Output -

** Original Linked List **

Data : 1, Node Address : com.anjan.clone.Node@7852e922, Next Data : 2, Random Data : 3

Data : 2, Node Address : com.anjan.clone.Node@4e25154f, Next Data : 3, Random Data : 1

Data : 3, Node Address : com.anjan.clone.Node@70dea4e, Next Data : 4, Random Data : 2

Data : 4, Node Address : com.anjan.clone.Node@5c647e05, Next Data : 5, Random Data : 4

Data : 5, Node Address : com.anjan.clone.Node@33909752, Next Data : null, Random Data : 5

** Cloned Linked List **

Data : 1, Node Address : com.anjan.clone.Node@55f96302, Next Data : 2, Random Data : 3

Data : 2, Node Address : com.anjan.clone.Node@3d4eac69, Next Data : 3, Random Data : 1

Data : 3, Node Address : com.anjan.clone.Node@42a57993, Next Data : 4, Random Data : 2

Data : 4, Node Address : com.anjan.clone.Node@75b84c92, Next Data : 5, Random Data : 4

Data : 5, Node Address : com.anjan.clone.Node@6bc7c054, Next Data : null, Random Data : 5

For the above program, the Time Complexity for cloning the Linked list is O(n).