Reverse a Linked list

Reverse a Linked list

---

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.

Reverse linked list in Java

---

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

Node.java

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

---

Knapsack Problem using Dynamic Programming in Java.

Why Selection sort is faster than Bubble sort.

Tower Of Hanoi Program in Java.

Java Multithreading and Concurrency Interview Questions and Answers with Example.

Find middle element of a linked list.

Transpose of Matrix Inplace.

Print Fibonacci series using Recursive approach in Java.

Enjoy !!!! 

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