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,
We will clone Linked list using below 2 approaches,
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.
Node.java
CloneLinkedList.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,
- Recursive approach
- Iterative 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.
Post a Comment