If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
In this post, we will see how to reverse a linked list in java.
This is one of popular interview question.
Java Linked List Interview Programs:
- How to reverse a linked list in pairs
- How to find middle element of linked list in java
- How to detect a loop in linked list in java
- Find start node of loop in linkedlist
- How to find nth element from end of linked list
- How to check if linked list is palindrome in java
- Add two numbers represented by linked list in java
There can be two solution to reverse a linked list in java
- 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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 to reverse a linkedlist will be :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
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:
|
1 2 3 4 5 |
5 6 7 1 2 After reversing 2 1 7 6 5 |
Recursive
|
1 2 3 4 5 6 7 8 9 10 11 12 |
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.
That’s all about reverse a linked list in java.
I searched google like hundreds of time … but all are hazy to understand the basic concept of linkedList .. Thanks a lot .. You simply done a great job .. It is very helpful for the beginner and the people who are taking preparation for their first job… 🙂
Hi there is something wrong in the recursive 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;
}
when it reaches the last node, then how call you call node.next.next
the recursion stops in the second last node when you have the node.next = null.
Suppose I have my list as 2 4 5 6
In this case when I call 5.next = 6 then the node.next value wil be null and it will return 6 .
so the node.next.next is actually 5.next.next = 6.next which is going to be pointed to 5 .
Hope I am not confusing you. 🙂
Hello
I think that in this condition
if (node == null || node.next == null) {
return node;
}
is abit vague because you do not set the head in this recursive function. By the end of the function, the head is lost.
If i am wrong, Could you please exaplain how the function works?
this one of best website for algorithem impl. very nice implementation.