Be the first user to complete this post

  • 0
 Add to List

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)

Code:


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

Also Read: