Reversing a Linked List

There are multiple ways of solving this problem  :

1. Using Recursion in the O(n) time & O(n) space complexity: 

 /**

 * @author sachin

 *

 */


public class LinkedListDemo {

 static Node head;

 static class Node{

  int data;

  Node next;

  public Node(int data) {

   this.data = data;

   next = null;

  }

 }



 static void printList(Node head){

  while(head!=null){

   System.out.println(head.data + " ");

   head = head.next;

  }

 }

 static void recursiveReverse(Node head)  {

//Base condition

  if(head ==null ){

      return; 

  }

  recursiveReverse(head.next);

  System.out.println(head.data + " ");

 }

 public static void main(String[] args) {

  

LinkedListDemo.head = new Node(25);

  LinkedListDemo.head.next = new Node(35);

  LinkedListDemo.head.next.next = new Node(14);

  LinkedListDemo.head.next.next.next = new Node(12);

  System.out.println("Original Linked list is :");

  LinkedListDemo.printList(head);

  System.out.println("Reversed linked list : ");

  LinkedListDemo.recursiveReverse(head);

 }

}
Output: 


Original Linked list is :

25 

35 

14 

12 

Reversed linked list : 

12 

14 

35 

25 
 

2. Using Iteration  in time O(n) & space O(1) complexity : 

This approach follows takes 3 Nodes   current[head node] , next and previous , head node is looped to move forward and prev node follows it as below :

Before iteration :

head --> 1 --> 2 --> 3 --> 4 --> 5--> null

Node current = head;

Node next = null;

Node prev = null;

//iterate the head node to the end or till the null is found

while(current!=null){

next = current.next;  //get the next node N

current.next=prev;  //next node N assigned the value of prev node

prev = current; //prev node is assigned to current node

current = next; // current node is assigned to next node 

}

head = prev;  //head is assigned to prev node which has the node detail in reverse order 

After iteration :

null <--1 <-- 2 <-- 3 <-- 4 <-- 5  <--- head

  

/**


 * @author sachin


 *


 */


public class LinkedListDemo {


 static Node head;


 static class Node{


  int data;


  Node next;


  public Node(int data) {


   this.data = data;

            next = null;


  }


 }


 static Node reverse(Node head){



  Node current = head;

  Node next = null;

  Node prev = null;

  while(current!=null){

   next = current.next;

   current.next=prev; 

   prev = current;

   current = next;

  }

  head = prev;

  return head;

 }

 static void printList(Node head){

  while(head!=null){

   System.out.println(head.data + " ");

   head = head.next;

  }

 }


 

 public static void main(String[] args) {


  LinkedListDemo.head = new Node(25);


  LinkedListDemo.head.next = new Node(35);


  LinkedListDemo.head.next.next = new Node(14);


  LinkedListDemo.head.next.next.next = new Node(12);


  System.out.println("Original Linked list is :");


  LinkedListDemo.printList(head);


  System.out.println("Reversed linked list : ");


  head = LinkedListDemo.reverse(head); //getting the head node after reversal


  LinkedListDemo.printList(head);


 }



}

Output : 

Original Linked list is :

25 

35 

14 

12 

Reversed linked list : 

12 

14 

35 

25 

 

Enjoy the coding !!!