In this post we’ll see a Java program to reverse a linked list.

### Reversing a linked list

__Linked list data structure__ as we know contains node where each node refers to the next node. That’s how each node of the
linked list can be reached even if nodes are not stored in contiguous memory. If we have to reverse a linked list
“*previous node refers the next node*” should be reversed and the next node should point to the previous node instead.

As you can see apart from changing the references to the next node, head should also be changed so that it points to the first node after the reversal of the linked list.

Java program to reverse a linked list can be written using both-

### Java program to reverse a linked list - Iterative

For the Java program to reverse a linked list using iterative method you need three instances of Node- **previous**, **current** and **next**.
As the names suggest **current** points to the current node in the iteration, **previous** points to the node on the left of the current node (null when current points to first node) and **next** points to the node on the right of the current node.

Iterate the linked list until current is null. In each iteration-

next = current.next; // that’s where reference is reversed current.next = previous; // Move forward by one node previous = current; current = next;Following image shows how it works using three nodes.

**Java code**

public class LinkedListReversal { private Node head; LinkedListReversal(){ head = null; } static class Node{ //data int i; Node next; Node(int i){ this.i = i; this.next = null; } public void displayData(){ System.out.print(" " + i); } } // Method to add nodes to linked list public void insertLast(Node newNode){ if(isEmpty()){ head = newNode; }else{ Node current = head; // traverse to the last of the list while(current.next != null){ current = current.next; } // adding new node, current last node // starts referencing to this new node current.next = newNode; } } public boolean isEmpty(){ return head == null; } //Method for reversing linked list public void reverseList(){ Node previous = null; Node current = head; Node next; while(current != null){ next = current.next; // that’s where reference is reversed current.next = previous; // Move forward by one node previous = current; current = next; } // By the end of traversal previous is at the // last node which becomes the head after reversal head = previous; } // Method to traverse and display all nodes public void displayList(){ Node current = head; while(current != null){ current.displayData(); current = current.next; } } public static void main(String[] args) { LinkedListReversal list = new LinkedListReversal(); list.insertLast(new Node(10)); list.insertLast(new Node(20)); list.insertLast(new Node(30)); list.insertLast(new Node(40)); list.insertLast(new Node(50)); System.out.println("Original linked list"); list.displayList(); list.reverseList(); System.out.println(""); System.out.println("Reversed linked list"); list.displayList(); } }

__Output__

Original linked list 10 20 30 40 50 Reversed linked list 50 40 30 20 10

### Java program to reverse a linked list – Recursive

In the recursive method for reversing a linked list method is called passing the first node then the method is recursively called by passing the next node (node.next).

Base case is when node.next is null.

public class LinkedListReversal { private Node head; LinkedListReversal(){ head = null; } static class Node{ //data int i; Node next; Node(int i){ this.i = i; this.next = null; } public void displayData(){ System.out.print(" " + i); } } // Method to add nodes to linked list public void insertLast(Node newNode){ if(isEmpty()){ head = newNode; }else{ Node current = head; // traverse to the last of the list while(current.next != null){ current = current.next; } // adding new node, current last node // starts referencing to this new node current.next = newNode; } } public boolean isEmpty(){ return head == null; } //Method for reversing linked list - recursive public Node reverseListRecursive(Node current){ // base case if(current.next == null){ return current; } Node node = reverseListRecursive(current.next); // that’s where reference is reversed current.next.next = current; current.next = null; return node; } // Method to traverse and display all nodes public void displayList(){ Node current = head; while(current != null){ current.displayData(); current = current.next; } } public static void main(String[] args) { LinkedListReversal list = new LinkedListReversal(); list.insertLast(new Node(10)); list.insertLast(new Node(20)); list.insertLast(new Node(30)); list.insertLast(new Node(40)); list.insertLast(new Node(50)); System.out.println("Original linked list"); list.displayList(); Node node = list.reverseListRecursive(list.head); // change the head list.head = node; System.out.println(""); System.out.println("Reversed linked list"); list.displayList(); } }

__Output__

Original linked list 10 20 30 40 50 Reversed linked list 50 40 30 20 10

In the recursive method reference is reversed in the following line

current.next.next = current;

Following image tries to clarify what this line does.

That's all for this topic **How to Reverse a Linked List in Java**. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

__Related Topics__

**You may also like-**

## No comments:

## Post a Comment