Be the first user to complete this post
|
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:
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: