Reverse a Linked list in Java Program

Reverse a Linked list OR
Reverse a Singly linked list Iteratively.

---

Let's see, how to Reverse a Singly linked list Iteratively 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 (Iterative 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 javabypatel;

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

You may also like to see

---

Reverse Linked list using Recursion

Detect loop in linked list

Reverse Linked list in Java

Find Nth node from last in a linked list

Sort Linked list.

Clone Linked list.

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.