reverse a linked list in java

Table of Contents

Java Linked List Interview Programs:
Iterative
Recursive

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:

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.


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 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 :


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

    }

}

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

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

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=nullis 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.

Was this post helpful?

Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.

Comments

Sajjad Islam says:

July 29, 2015 at 3:57 pm

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… 🙂

rohit says:

December 30, 2015 at 4:34 pm

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

1. MKB says:
  
  January 14, 2016 at 11:05 pm
  
  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. 🙂
  
calvinraveenthran says:

January 10, 2016 at 4:55 am

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?

Jitendra Chopra says:

September 21, 2018 at 7:49 pm

this one of best website for algorithem impl. very nice implementation.