Reverse a Linked List

Objective: Reverse the given linked list.

Input: A Linked List

Output: Reversed Linked List

Example:

Input : ->30->25->20->15->10->5

Reversed : ->5->10->15->20->25->30

NOTE : Click Reverse a Linked List – Part 2 to see the another implementation of this problem.

Approach:

Iterative:

  • Create 3 nodes, currNode, PrevNode and nextNode.
  • Initialize them as currNode = head; nextNode = null;prevNode = null;
  • Now keep reversing the pointers one by one till currNode!=null.
   while(currNode!=null){
     nextNode = currNode.next;
     currNode.next = prevNode;
     prevNode = currNode;
     currNode = nextNode;
}
  • At the end set head = prevNode;
  • See Example:

Linked List Reversal

 

 

Note: If Image above is not clear, either zoom your browser or right click on image and open in a new tab.

 

  • Recursive Approach:
    • Take 3 nodes as Node ptrOne,Node ptrTwo, Node prevNode
    • Initialize them as ptrOne = head; ptrTwo=head.next, prevNode = null.
    • Call reverseRecursion(head,head.next,null)
    • Reverse the ptrOne and ptrTwo
    • Make a recursive call for reverseRecursion(ptrOne.next,ptrTwo.next,null)

    Complete Code:


    Output:

    ->30->25->20->15->10->5
    Reverse Through Iteration
    ->5->10->15->20->25->30
    ___________________
    Original Link List 2 : ->36->35->34->33->32->31
    Reverse Through Recursion
    ->31->32->33->34->35->36
    

     

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

  • Aman Rustagi
  • Tom Grimberg

    there is a tiny mistake of numbering in the second stage picture
    of reversing the linked list,
    sould be like before: prevNode = currNode; step 3
    currNode = nextNode; step 4

  • iOSeTutorials (Sheldon)

    can u really access prev node if it is a singly linked list?

    • iOSeTutorials (Sheldon)

      I think it should be as easy as:
      currentNode = list.head
      while (currentNode.next != nil) {

      }

  • Paul

    The recursive recurse method is flawed. What if the linked list is empty or contains only 1 element? It crashes…

  • rahul1906

    Here is better way for recursion –

    public void reverseRecursion(Node curnode,Node prevnode){
    if(curnode == null){
    System.out.println(“n Reverse Through Recursion”);
    display(prevnode);
    return;
    }
    Node nextnode = curnode.next;
    curnode.next = prevnode;
    prevnode = curnode;
    curnode = nextnode;
    reverseRecursion(curnode,prevnode);
    }

  • Alejandro Casanas

    for a video explanation check our this video https://www.youtube.com/watch?v=DKn7GaMVi8M

%d bloggers like this: