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.

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.

Java program to reverse a linkedlist will be :

Run above program, you will get following output:

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

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.


import_contacts

You may also like:

Related Posts

  • 12 August

    Intersection of two linked lists

    If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. In this post, we will see how to find Intersection of two linked lists. Problem Given two singly linked lists, find if two linked lists intersect. If they intersect, find intersection point. Solution Here is simple algorithm to […]

  • 12 October

    Implement Queue using Linked List in java

    If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. In this post , we will see how to implement Queue using Linked List in java. Queue is abstract data type which demonstrates First in first out (FIFO) behaviour. We will implement same behaviour using Array. Although java provides implementation […]

  • 10 October

    Convert sorted Linked List to balanced BST

    If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. In this post , we will see how to convert sorted LinkedList to balanced binary search tree. There are two ways to do it. Solution 1: It is very much similar to convert sorted array to BST. […]

  • 20 September

    Find length of Linked List in java

    If you want to practice data structure and algorithm programs, you can go through data structure and algorithm programs. In this post, we will see how to find length of Linked List in java. You can obviously use size() method of java Linked List class but here we are going to see how to find length […]

  • 20 September

    Implement singly linked list in java

    In this post, we will see how to implement singly linked list in java. It is one of the most used data structure. In singly linked list, Node has data and pointer to next node. It does not have pointer to the previous node. Last node ‘s next points to null, so you can iterate […]

  • 10 September

    Implement stack using Linked List in java

    If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. In this program, we will see how to implement stack using Linked List in java. The Stack is an abstract data type that demonstrates Last in first out (LIFO) behavior. We will implement the same behavior using […]

Comments

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

  2. 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. 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. 🙂

  3. 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?

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.