Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Reverse a Linked List

Objec­tive: Reverse the given linked list.

Input: A Linked List

Out­put: Reversed Linked List

Exam­ple:

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 imple­men­ta­tion of this problem.

Approach:

Iter­a­tive:

  • Cre­ate 3 nodes, cur­rN­ode, Pre­vN­ode and nextNode.
  • Ini­tial­ize them as cur­rN­ode = head; nextN­ode = null;pre­vN­ode = null;
  • Now keep revers­ing the point­ers 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 Exam­ple:
  • Linked List Reversal

    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.

     

  • Recur­sive Approach:
    • Take 3 nodes as Node ptrOne,Node ptrTwo, Node prevNode
    • Ini­tial­ize them as ptrOne = head; ptrTwo=head.next, pre­vN­ode = null.
    • Call reverseRecursion(head,head.next,null)
    • Reverse the ptrOne and ptrTwo
    • Make a recur­sive call for reverseRecursion(ptrOne.next,ptrTwo.next,null)

    Com­plete Code:


    Out­put:

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

     

You may also like...

  • Aman Rustagi
  • Tom Grim­berg

    there is a tiny mis­take of num­ber­ing in the sec­ond stage pic­ture
    of revers­ing the linked list,
    sould be like before: pre­vN­ode = cur­rN­ode; step 3
    cur­rN­ode = nextN­ode; step 4

  • iOSe­Tu­to­ri­als (Sheldon)

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

    • iOSe­Tu­to­ri­als (Sheldon)

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

      }

  • Paul

    The recur­sive recurse method is flawed. What if the linked list is empty or con­tains only 1 ele­ment? It crashes…

  • rahul1906

    Here is bet­ter way for recursion —

    pub­lic void reverseRecursion(Node curnode,Node pre­vn­ode){
    if(curnode == null){
    System.out.println(“n Reverse Through Recur­sion”);
    display(prevnode);
    return;
    }
    Node nextn­ode = curnode.next;
    curnode.next = pre­vn­ode;
    pre­vn­ode = curn­ode;
    curn­ode = nextn­ode;
    reverseRecursion(curnode,prevnode);
    }