Reverse a Linked List – Part 2

This post is the extension of our earlier post Reverse a linked list. Here We have provided the better recursive solution in which we start reversing the list from the end.

Objective: Reverse the given linked list.

Input: A Linked List

Output: Reversed Linked List

Example:

Original List :->10->8->6->4->2
Reversed List :->2->4->6->8->10

Approach:

Recursion:

  • Traverse till the end of list through recursion.
  • Make the last node as head.
  • Now you are at the end of the list and rest of the nodes are stores in a stack
  • Now while coming back, each node will pop out from the stack in reverse order
  • take these nodes and start pointing it to next node coming out of stack.
reverse Linked List - Part 2
reverse Linked List – Part 2

Complete Code:

public class reverseLinkedList2 {
public static Node head=null;
public Node reverseRecur2(Node current){
if(current==null){
return null;
}
if(current.next==null){
head = current;
return null;
}
reverseRecur2(current.next);
current.next.next = current;
current.next = null;
return head;
}
public void display(Node head){
//
Node currNode = head;
while(currNode!=null){
System.out.print("->" + currNode.data);
currNode=currNode.next;
}
}
public static void main(String args[]){
head = new Node(10);
head.next = new Node(8);
head.next.next = new Node(6);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(2);
System.out.println("Original List :");
reverseLinkedList2 r= new reverseLinkedList2();
r.display(head);
System.out.println("\nReversed List :");
Node x = r.reverseRecur2(head);
r.display(x);
}
}
class Node{
public int data;
public Node next;
public Node(int data){
this.data = data;
this.next = null;
}
}

Output:
Original List :
->10->8->6->4->2
Reversed List :
->2->4->6->8->10