Clone Linked list in Java

Copy linked list in Java

---

Given a Linked list, Create a deep copy of Linked list.

Lets understand the problem statement graphically and it will be more clear,

Algorithm

---

We will clone Linked list using below 2 approaches, 

1. Recursive approach
2. Iterative approach.

Recursive approach:
In this approach we will recursively create a new Node(clone node) in each recursive call and start assigning next pointer of each node when recursive call returns.
 

Iterative approach: 
In this approach we need to take care of cloned start node, initialy it will be null, and after creation of first node we will assign that node to cloned start node and preserve start node for returning back to caller.

After creating cloned start node, we will create further Nodes iteratively and assign next pointer of previously created node to newly created node.

For keeping track of previously created node, we need to take one pointer which store reference of Node created in previous iteration.

Clone Linked List Java Program

---

Node.java

package javabypatel;

public class Node {
 private int data;
 private Node next;

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

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }

 public Node getNext() {
  return next;
 }

 public void setNext(Node next) {
  this.next = next;
 }
}

CloneLinkedList.java

package javabypatel;

public class CloneLinkedList {

 Node startNode;

 public static void main(String[] args) {
  new CloneLinkedList();
 }

 public CloneLinkedList () {
  Node node1 = new Node(1);
  Node node2 = new Node(2);
  Node node3 = new Node(3);
  Node node4 = new Node(4);

  node1.setNext(node2);
  node2.setNext(node3);  
  node3.setNext(node4);

  this.startNode = node1;

  Node clonedStart1 = cloneLinkedListIterative(startNode);
  printNodes(clonedStart1);

  Node clonedStart2 = cloneLinkedListRecursive(startNode);
  printNodes(clonedStart2);
 }

 private Node cloneLinkedListIterative(Node startNode) {
  if (startNode == null)
   return null;

  Node cloneStart = null;
  Node previousNode = null;

  while(startNode!=null){

   Node temp = new Node(startNode.getData());

   if(cloneStart == null){
    cloneStart = temp;
    previousNode = temp;

   }else{
    previousNode.setNext(temp);
    previousNode = temp;
   }
   startNode = startNode.getNext();
  }
  return cloneStart;
 }

 private Node cloneLinkedListRecursive(Node startNode) {
  if(startNode == null){
   return null;
  }
  Node temp = new Node(startNode.getData());
  temp.setNext(cloneLinkedListRecursive(startNode.getNext()));
  return temp;
 }

 public void printNodes(Node startNode){
  System.out.println();
  if(startNode==null)
   return;

  Node temp = startNode;
  while(temp!=null){
   System.out.print( temp.getData() + " ");
   temp = temp.getNext();
  }
 }
}

You may also like to see

---

Exception Handling Interview Question-Answer

Method Overloading - Method Hiding Interview Question-Answer

Advanced Multithreading Interview Questions-Answers In Java

Type Casting Interview Questions-Answers In Java

How Thread.join() in Java works internally

How is ambiguous overloaded method call resolved in java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.