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:

public class ReverseLinkedList {
public static void main (String[] args) throws java.lang.Exception
{
LinkedListT a = new LinkedListT();
a.addAtBegin(5);
a.addAtBegin(10);
a.addAtBegin(15);
a.addAtBegin(20);
a.addAtBegin(25);
a.addAtBegin(30);
// System.out.print("Original Link List 1 : ");
a.display(a.head);
a.reverseIterative(a.head);
LinkedListT b = new LinkedListT();
b.addAtBegin(31);
b.addAtBegin(32);
b.addAtBegin(33);
b.addAtBegin(34);
b.addAtBegin(35);
b.addAtBegin(36);
System.out.println("");
System.out.println("___________________");
System.out.print("Original Link List 2 : ");
b.display(b.head);
b.reverseRecursion(b.head,b.head.next,null);
System.out.println("");
//b.display(x);
}
}
class Node{
public int data;
public Node next;
public Node(int data){
this.data = data;
this.next = null;
}
}
class LinkedListT{
public Node head;
public LinkedListT(){
head=null;
}
public void addAtBegin(int data){
Node n = new Node(data);
n.next = head;
head = n;
}
public void reverseIterative(Node head){
Node currNode = head;
Node nextNode = null;
Node prevNode = null;
while(currNode!=null){
nextNode = currNode.next;
currNode.next = prevNode;
prevNode = currNode;
currNode = nextNode;
}
head = prevNode;
System.out.println("\n Reverse Through Iteration");
display(head);
}
public void reverseRecursion(Node ptrOne,Node ptrTwo, Node prevNode){
if(ptrTwo!=null){
if(ptrTwo.next!=null){
Node t1 = ptrTwo;
Node t2 = ptrTwo.next;
ptrOne.next = prevNode;
prevNode = ptrOne;
reverseRecursion(t1,t2, prevNode);
}
else{
ptrTwo.next = ptrOne;
ptrOne.next = prevNode;
System.out.println("\n Reverse Through Recursion");
display(ptrTwo);
}
}
else if(ptrOne!=null){
System.out.println("\n Reverse Through Recursion");
display(ptrOne);
}
}
public void display(Node head){
//
Node currNode = head;
while(currNode!=null){
System.out.print("->" + currNode.data);
currNode=currNode.next;
}
}
}


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