How do you reverse a singly linked list?

How to reverse a linked list is one of the most commonly asked data structures interview questions. Here we have both an iterative and a recursive solution for this problem. Let’s start with the iterative solution.

Reverse a linked list iteratively




First off, in case you don’t already know, the word ‘iterative’ when used in problems like these basically means that we use some sort of loop to solve the problem – whether it’s a while loop, a for loop, or whatever type of loop you desire to use. We choose to use a while loop to come up with a solution.

Let’s assume that we are going to start reversing the linked list starting from the very first node – the head node. What it basically comes down to is changing pointers from one node to the next so that the entire linked list becomes reversed. There is definitely a process – an algorithm – that we will want to follow in order to do that:

Reverse a linked list iterative algorithm

1. The head node’s next pointer should be set to NULL since the head will become the tail. This is an exception for the head node, and can be done outside the while loop. But, before we do this we will need a temp variable to point to the 2nd node (the node after the head node), because the only way to reference the 2nd node is through the head node’s next pointer.

2. The 2nd node (the node after the head node) should have it’s own next pointer changed to point to the head node. This will reverse the order of the nodes. But, remember that the 2nd node’s next pointer will at first be pointing to the 3rd node. This means that before we change the 2nd node’s next pointer, we have to save a reference to the 3rd node otherwise we will have no way of referencing the 3rd node. So, we simply store a reference to the 3rd node in a variable before we change the 2nd node’s next pointer.

3. The 3rd node then becomes the “first” node in the while loop and we repeat the process of changing pointers described in step 2.

4. Continue step 3 until we come across a node that has a next pointer set to NULL. When we do come across a NULL next pointer we just set the head node to point to the node that has the NULL next pointer. This node was previously the tail node, but is now the head node because we are reversing the linked list.

Reverse a linked list iterative solution in Java


public reverseListIteratively (Node head)
{
if (head == NULL || head.next == NULL)
return;  //empty or just one node in list

Node Second = head.next;

//store third node before we change 
Node Third = Second.next;  

//Second's next pointer
Second.next = head;  //second now points to head
head.next = NULL;  //change head pointer to NULL

//only two nodes, which we already reversed
if (Third == NULL)
return;  

Node CurrentNode = Third;

Node PreviousNode = Second;

while (CurrentNode != NULL)
{ 
Node NextNode = CurrentNode.next;

CurrentNode.next = PreviousNode;

/*  repeat the process, but have to reset
     the PreviousNode and CurrentNode
*/

PreviousNode = CurrentNode;
CurrentNode = NextNode;  
}

head  = PreviousNode; //reset the head node
}

Here’s an image that may help you visualize running the code above:

Reverse a linked list recursive Java

Now, let’s find a recursive solution in Java for this problem. The advantage that we have with recursion is the fact that we can go to the very end of the linked list and work backwards to reverse the list starting from the every end. This is because with recursion we can go to the very end of the linked list, but also essentially “save” our place in each and every node we traverse so that we can go backwards and change the pointers in the linked list so that the list is reversed – if you are rusty on recursion you can read our Recursion tutorial.

Base case for recursive solution

Before we come up with our recursive case, we should come up with our base case for this problem. The base case is what we use to essentially stop the recursion from continuously running. So, when should we stop the recursion from running – try to see if you can come up with this scenario on your own.

The base case for this problem will actually occur whenever we reach the tail node of the linked list – and by “tail” node we mean the very last node. We will know that we have reached the tail node when the current node’s next node is NULL – so the current node will be the tail node.

What should be done in the base case for this recursive problem?




Now, we know what the base case is and how to check for it, but what exactly should we be doing in this case? Well, we obviously want to have a return statement so that we can put a stop to the recursion. But, is there anything else that we should be doing here as well? It turns out that there is something else we need to do in the base case, because in the base case we are at the very end of the linked list. This means that because we are trying to reverse the list, we need to set the head pointer to point to the very last node.

This means that our base case would look like this – remember that we are assuming that in the recursive case, we will just be passing in the very next node in the linked list to the recursive function:

Java code for recursive solution’s base case:

/* if we are at the TAIL node: 
*/
if(currentNode.next == NULL) 
{ 
//set HEAD to TAIL since we are reversing list
head = currentNode; 
return; //since this is the base case
}

Coming up with a recursive case

Now that we’ve come up with the base case in Java, what about the recursive case? Well, in the recursive case we will clearly need to change the pointers so that the nodes are reversed. For a given node – let’s say we are dealing with node 99 in the linked list image above – the Node coming after node 99 (node 37) is represented by Node 99 -> next. If we want node 37 to point back to node 99 (which is what we would want if we are reversing the nodes), then we would set the next pointer of node 37 to point back to Node 99, which in pseudocode would look like Node99 -> next -> next = Node 99.

We would also need to get rid of the pointer from node 99 to node 37 so we would have to set Node 99 -> next to NULL.

So, now we can come up with this code that would be our final recursive answer to the problem of reversing a singly linked list:

Reverse a linked list recursive Java solution


public void recursiveReverse(Node currentNode )
{  
 //check for empty list 
 if(currentNode == NULL)
    return;

/* if we are at the TAIL node:
    recursive base case:
 */
if(currentNode.next == NULL) 
{ 
//set HEAD to current TAIL since we are reversing list
head = currentNode; 
return; //since this is the base case
}

recursiveReverse(currentNode.next);
currentNode.next.next = currentNode;
currentNode.next = null; //set "old" next pointer to NULL
}

Summary of recursive solution to reversing a linked list

The cool thing about recursion in this problem is that it essentially allows us to iterate through the linked list backwards – even though this is impossible in a singly linked list just by using the pointers (or course this would certainly be possible in a doubly linked list). The reason we can do this in recursion is because of the fact that the stack frames for each function call are saved until we get to the very end of the list, and then it is as if we are ‘unwinding’ the stack frames one by one going backwards in the linked list – where each stack frame essentially represents a node in the linked list. Make sure you understand this point, because it is important and really helps in your understanding of how to use recursion to solve problems.

Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.

  • Mason Jones

    And this is why recursion sucks!

  • Sandeep

    Very Good Explanation sir. I have understood very easily, Thank you so much sir.

  • Thanks for the wonderful article. I have always found this amazing. Reversing a linked list is not a magic or does not require remembering the code… It is a simple dynamics, here is how we can visualize the same
    http://techieme.in/reversing-a-singly-linked-list/

  • Han

    Do you think the void version will work correctly?

  • prashant chaudhary

    public class Link {

    int a;

    Link Next;

    public Link(int i){

    a=i;

    }

    }

    ——————————————————

    public class LinkList {

    Link First = null;

    public void insertFirst(int a){

    Link objLink = new Link(a);

    objLink.Next=First;

    First = objLink;

    }

    public void displayLink(){

    Link current = First;

    while(current!=null){

    System.out.println(current.a);

    current = current.Next;

    }

    }

    public void ReverseLink(){

    Link current = First;

    Link Previous = null;

    Link temp = null;

    while(current!=null){

    if(current==First)

    temp = current.Next;

    else

    temp=current.Next;

    if(temp==null){

    First = current;

    //return;

    }

    current.Next=Previous;

    Previous=current;

    //System.out.println(Previous);

    current = temp;

    }

    }

    public static void main(String args[]){

    LinkList objLinkList = new LinkList();

    objLinkList.insertFirst(1);

    objLinkList.insertFirst(2);

    objLinkList.insertFirst(3);

    objLinkList.insertFirst(4);

    objLinkList.insertFirst(5);

    objLinkList.insertFirst(6);

    objLinkList.insertFirst(7);

    objLinkList.insertFirst(8);

    objLinkList.displayLink();

    System.out.println(“—————————–“);

    objLinkList.ReverseLink();

    objLinkList.displayLink();

    }

    }

  • shailendra

    Node head = firstNode;
    Node current = head;
    while(current != null && current.next != null){
    Node temp = current.next;
    current.next = temp.next;
    temp.next = head;
    head = temp;

    }

  • DK

    The last line “head = PreviousNode; //reset the head node”
    has no effect from the method caller’s perspective, as the reference to the head node argument to the method is passed by value (not be reference). Wouldn’t it be better to return PreviousNode as the last line in the method?

  • muki buki

    /*

    * Reverses the linked list with the head h and returns the new head (previous tail)

    * time complexity: O(n)

    * space complexity: O(1)

    */

    private static Node reverse(Node h) {

    if (h == null || h.next() == null) {
    return h;
    }

    // tracks the previous node (starts with null)
    Node prev = null;

    // tracks the current node (starts with h)
    Node curr = h;

    // temporary holds the next link
    Node t = null;

    while((t=curr.next()) != null) {
    curr.setNext(prev);
    prev = curr;
    curr = t;
    }

    // now current is the previous tail
    curr.setNext(prev);

    // returns the previous tail / new root
    return curr;
    }

  • Patanjal

    Node ReverseListIteratively(Node head)
    {
    if (head == null) return head;

    Node current = head;
    Node previous = null;

    while (true)
    {
    Node OriginalNext = current.next;
    current.next = previous;
    if (OriginalNext == null)
    {
    //current is the last element hence return it
    return current;
    }
    else
    {
    previous = current;
    current = OriginalNext;
    }
    }
    }

  • asfend

    How to delete values from linked list means to say how to empty list step by step

  • Sunil

    private Node reverseList(Node head) {

    if(head == null)

    return null;

    Node temp = reverseList(head.next);

    if(temp == null) {

    newHead = head;

    } else {

    temp.next = head;

    head.next = null;

    }

    return head;

    }

  • aspir

    Your recursive version is a little difficult to understand, I write one below, the main idea of which is divide the whole list into sub ones, and save its direct ancestor list’s head node, and assume the sub list is reversed, return the tail node of the sub list by the recursively call, and let the tail point to the saved head node:

    Node reverseList(Node head) {
    Node first = new Node();
    doReverse(first, head);
    return first.next; // return the new head node
    }

    Node doReverse(Node first, Node head) {
    static int i = 0;
    if (head == NULL || head.next == NULL) {
    if (i == 0) first.next = head; // save the new head node
    return head;
    }

    Node tail = head;
    Node preTail = doReverse(head.next);
    preTail.next = tail;
    tail.next = NULL;

    i++;

    return tail;

    }

  • kevin

    sorry, my bad…

  • kevin

    for the iter code, in the while loop, you did not reset the previous node.

  • Wing

    Iteration: Time O(n), Space:O(1)
    Recursion: Time O(n), Space O(n) stack overhead

  • varoon10

    Thanks Waqas you are right!

  • varoon10

    You are right – I've updated the code – thanks for taking the time to post!

  • varoon10

    You're right Chanchal, the code has been updated – the last line is now currentNode.next = null; which will do that for us.

    Thanks for the post!

  • Waqas

    Yep I also think your last line will be added to the code otherwise new tail will not be pointing to NULL.

  • mine

    Thank you for your excellent work. In your recursive reverse shouldn't you be doing currentNode.next = null to make sure there is no cycle?
    public void recursiveReverse(Node currentNode )
    {
    …….
    recursiveReverse(currentNode.next);
    currentNode.next.next = currentNode;
    //currentNode.next = null; ???
    }

  • Chanchal Raj

    On reverse, the last element (which was first before), will not have a NULL pointer at the end acc to this algo, cud u please check it

  • ru

    what is the time and space complexity