How to reverse a linked list in java

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
This is one of popular interview question.

Java Linked List Interview Programs:

    How to detect a loop in linked list in java Find start node of loop in linkedlist How to find middle element of linked list in java How to find nth element from end of linked list How to reverse a linked list in java Add two numbers represented by linked list in java
There can be two solution for reversing linked list
  • Iterative
  • Recursive

Iterative:

Logic for this would be:
  • Have three nodes i.e previousNode,currentNode and nextNode
  • When currentNode is starting node, then previousNode will be null
  • Assign currentNode.next to previousNode to reverse the link.
  • In each iteration move currentNode and previousNode by  1 node.
public static Node reverseLinkedList(Node currentNode)
 {
// For first node, previousNode will be null
Node previousNode=null;
  Node nextNode;
  while(currentNode!=null)
  {
   nextNode=currentNode.next;
  // reversing the link
   currentNode.next=previousNode;
  // moving currentNode and previousNode by 1 node
   previousNode=currentNode;
   currentNode=nextNode;
  }
  return previousNode;
 }
Java program for this will be :
package org.arpit.java2blog;

public class LinkedList{

 private Node head;

 private static class Node {
  private int value;
  private Node next;

  Node(int value) {
   this.value = value;

  }
 }

 public void addToTheLast(Node node) {

  if (head == null) {
   head = node;
  } else {
   Node temp = head;
   while (temp.next != null)
    temp = temp.next;

   temp.next = node;
  }
 }


 public void printList(Node head) {
  Node temp = head;
  while (temp != null) {
   System.out.format("%d ", temp.value);
   temp = temp.next;
  }
  System.out.println();
 }

 // Reverse linkedlist using this function 
public static Node reverseLinkedList(Node currentNode)
 {
// For first node, previousNode will be null
Node previousNode=null;
  Node nextNode;
  while(currentNode!=null)
  {
   nextNode=currentNode.next;
  // reversing the link
   currentNode.next=previousNode;
  // moving currentNode and previousNode by 1 node
   previousNode=currentNode;
   currentNode=nextNode;
  }
  return previousNode;
 }

 public static void main(String[] args) {
  LinkedList list = new LinkedList();
  // Creating a linked list
  Node head=new Node(5);
  list.addToTheLast(head);
  list.addToTheLast(new Node(6));
  list.addToTheLast(new Node(7));
  list.addToTheLast(new Node(1));
  list.addToTheLast(new Node(2));
 
  list.printList(head);
  //Reversing LinkedList
  Node reverseHead=reverseLinkedList(head);
  System.out.println("After reversing");
  list.printList(reverseHead);
 
 }

}

Run above program, you will get following output:
5 6 7 1 2 
After reversing
2 1 7 6 5 

Recursive:

Base case: Base case for this would be either node is null or node.next is null
For recursive solution, replace reverseLinkedList of above program to below function
public static Node reverseLinkedList(Node node) {
     if (node == null || node.next == null) {
         return node;
     }

     Node remaining = reverseLinkedList(node.next);
     node.next.next = node;
     node.next = null;
    return remaining;
 }
Output of this program will be same as above program.
Now lets understand logic for above recursive program.
5->6->7->1->2
Above function will terminate when last node(2) 's next will be null.so while returning when you reach at node with value 1,If you closely observe node.next.next=node is actually setting 2->1(i.e. reversing the link between node with value 1 and 2) and node.next=null is removing link 1->2. So in each iteration, you are reversing link between two nodes.
Below diagram will make it clear


Please go through java interview programs for more such programs.

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012