Reverse a Linked list in Java Program

Reverse a Linked list OR
Reverse a Singly linked list.


Let's see, how to Reverse a Singly linked list in Java, how to Reverse Linked list using recursion, and how to Reverse a Linked list iteratively.

There are 2 ways to Reverse a Linked list using,

1. Recursive Algorithm.
2. Iterative Algorithm.

 Lets understand what is the input and the expected output.

Algorithm


Reversing pointers of Linked list is very simple,
We just need to initialize 3 pointers, ptrA, ptrB and ptrC.

ptrA task is to point to first place.
(This pointer is used as reference for ptrB to point back, initially it will be null since last node in reversed list will be null.)

ptrB task is to point to second place.
(This pointer is the main pointer and we will start pointing ptrB's next to ptrA and this is the way we will reverse all the existing pointers link.)

ptrC task is to point to third place.
(This pointer is only for backup, so that we will not loose list ahead of ptrB, otherwise reference to list ahead of ptrB will be lost.)

STEP 1: We will start by setting ptrA to null, because ptrA is going to became tail node in reversed 
                list.
STEP 2: ptrB which is pointing to first node now is going to be tail node in reverse list, so we will 
                point ptrB's next to ptrA.
STEP 3: By above 2 step, if we have only 1 node in a list, then our task is done.
STEP 4. As soon as we point ptrB's next to ptrA in step 2, then we will loose reference to the list 
               ahead of ptrB, So before executing step 2, we will keep backup of ahead list to ptrC.



STEP 5. If we repeat the above steps till ptrB points to null which is indication that all nodes of 
                original list is reversed.


Java Program to Reverse linked list.


package linkedlist.singly;

public class ReverseTheLinkedList {
 
 Node startNode;
 
 public static void main(String[] args) {
  ReverseTheLinkedList reverseTheLinkedList = new ReverseTheLinkedList();
  reverseTheLinkedList.addNode(new Node(10));
  reverseTheLinkedList.addNode(new Node(20));
  reverseTheLinkedList.addNode(new Node(30));
  reverseTheLinkedList.addNode(new Node(40));
  reverseTheLinkedList.addNode(new Node(50));
  
  //Print List
  System.out.println("Original List is: ");
  reverseTheLinkedList.printLinkList(reverseTheLinkedList.startNode);
  
  Node reverseListHead = reverseTheLinkedList.reverseLinkList();
  
  //Reverse List
  System.out.println("\nReverse List is: ");
  reverseTheLinkedList.printLinkList(reverseListHead);
 }

 public Node reverseLinkList(){
  Node ptr1 = null;
  
  //For reversing original list, use startNode directly instead of ptr2.
  Node ptr2 = startNode;  
  
  while(ptr2!=null){
   Node ptr3 = ptr2.getNext();
   ptr2.setNext(ptr1);

   ptr1 = ptr2;
   ptr2 = ptr3;
  }
  
  //required for reversing original list.
  //At last startNode will point to null, but ptr1 will have fully reversed list, so pointing startNode to ptr1.
  //startNode = ptr1;
  
  return ptr1;
 }

 private void printLinkList(Node startNode) {
  Node tempNode = startNode;
  while(tempNode!=null){
   System.out.print(tempNode.getData() + " ");
   tempNode = tempNode.getNext();
  }
 }

 private void addNode(Node node) {
  if(startNode!=null){
   Node tempNode = startNode;
   while(tempNode.getNext()!=null){
    tempNode = tempNode.getNext();
   }
   tempNode.setNext(node);
  }else{
   this.startNode = node;
  }
 }
}


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;
 }
}


Stack trace of reversing Linked list in Java






Enjoy !!!! 

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

Post a Comment