Reverse a singly linked list in Java - Recursive and Iterative approach

Linked list reversal is common interview question. Linked list can be reverse in both iterative and recursive way. Recursive way is little bit difficult to code compare to iterative one.Iterative one is memory efficient when dealing with large number of nodes.In this post first we will first write sample code for linked list in recursive way and followed by the iterative approach. Download complete program.
Recursive approach :- When we think of reversal of linked list by recursion, the very first thing comes in mind - reach at end of list and come back to starting point. Lets write the sample code and understand each steps involved from associated in-line comments.

/* Reverse a singly linked list using recursion */
static public Node reverseLinkedListUsingRecursion(Node head) {
 /* Return null , if list is empty or head if head.next = null */
 if (head == null || head.getNext() == null) {
  return head;
 } else {
  /* Store next node of list */
  Node nextNode = head.getNext();
  /* For storing reference of last node of list */
  Node retHead = reverseLinkedListUsingRecursion(nextNode);
  /* Set next reference of the given node to null, breaking the chain */
  head.setNext(null);
  /* Add next reference in reverse order */
  nextNode.setNext(head);
  /* Return last node of the given list */
  return retHead;
 }
}

Iterative approach :- Writing iterative code is memory efficient and easy to understand.Below is the sample code for the same.Go through the in-line comments associated with each step.

/* Reverse a singly linked list */
static public Node reverseLinkedListIterative(Node head) {
 /* Return null , if list is empty or head if head.next Is null */
 if (head == null || head.getNext() == null) {
  return head;
 } else {
  Node previous = null;
  Node current = head;
  Node curNext;
  /* Iterate linked list and reverse the next reference for each node */
  while (current != null) {
   curNext = current.getNext();// Store next node for iteration
   current.setNext(previous); // set current next as previous
   /* store current in previous, for next iteration */
   previous = current;
   current = curNext;
  }
  /*
   * Once we complete the list iteration, previous refers to last
   * node, so assign that to head
   */
  head = previous;
 }
 return head;
}

Here is the complete sample program for the reversal of linked list using recursive and Iterative approach:-

package com.devinline.linkedlist;

public class ReverseSinglyLinkedlist {
 static Node head = null;

/* Reverse a singly linked list using recursion */
static public Node reverseLinkedListUsingRecursion(Node head) {
 /* Return null , if list is empty or head if head.next = null */
if (head == null || head.getNext() == null) {
 return head;
} else {
 /* Store next node of list */
 Node nextNode = head.getNext();
 /* For storing reference of last node of list */
 Node retHead = reverseLinkedListUsingRecursion(nextNode);
 /* Set next reference of the given node to null, breaking the chain */
 head.setNext(null);
 /* Add next reference in reverse order */
 nextNode.setNext(head);
 /* Return last node of the given list */
  return retHead;
 }
}

/* Reverse a singly linked list */
static public Node reverseLinkedListIterative(Node head) {
 /* Return null , if list is empty or head if head.next Is null */
if (head == null || head.getNext() == null) {
 return head;
} else {
 Node previous = null;
 Node current = head;
 Node curNext;
 /* Iterate linked list and reverse the next reference for each node */
 while (current != null) {
  curNext = current.getNext();// Store next node for iteration
  current.setNext(previous); // set current next as previous
  /* store current in previous, for next iteration */
  previous = current;
  current = curNext;
 }
 /*
  * Once we complete the list iteration, previous refers to last
  * node, so assign that to head
  */
  head = previous;
 }
 return head;
}

 private static Node createNewNode(int data) {
  /*Inner class Object creation*/
 return new ReverseSinglyLinkedlist().new Node(data);
}

/* Add New node at start of linked list */
private static void insertFirst(int data) {
 Node newNode = createNewNode(data);
 if (head == null) {
  head = newNode;
 } else {
  newNode.setNext(head);
  head = newNode;
 }
}

/* Display data of nodes/iterate linked list */
private static void iterateLinedList(Node head) {
 Node current = head;
 if (head != null) {
  System.out.print("[");
  while (current != null) {
   System.out.print(current.getData() + " ");
   current = current.getNext();
  }
  System.out.print(" ]\n");
 } else {
  System.out.println("Linked list is empty.");
 }

}

class Node {

 private int data;
 private Node next; // reference(handler) for next Node.

 public Node(int data) {
  this.data = data;
  this.next = null;
 }

 public Node getNext() {
  return next;
 }

 public void setNext(Node next) {
  this.next = next;
 }

 public int getData() {
  return data;
 }

}

public static void main(String[] args) {
 /* Setup a linked list */
 insertFirst(142);
 insertFirst(135);
 insertFirst(141);
 insertFirst(141);
 insertFirst(145);
 insertFirst(148);
 insertFirst(145);
 /* Original linked list display */
 System.out.println("Original linked list ");
 iterateLinedList(head);

 /* Reverse a singly linked list using recursion and display the same */
 Node newhead1 = ReverseSinglyLinkedlist
   .reverseLinkedListUsingRecursion(head);
 System.out.println("Reversed linked list(Recursive approach)  ");
 iterateLinedList(newhead1);

 /* Reverse a singly linked list using iterative and display the same */
 Node newhead2 = ReverseSinglyLinkedlist
   .reverseLinkedListIterative(newhead1);
 System.out.println("Reversed linked list(Iterative appraoch) ");
  iterateLinedList(newhead2);
 }

}

========Sample output==============
Original linked list
[145 148 145 141 141 135 142  ]
Reversed linked list(Recursive approach)
[142 135 141 141 145 148 145  ]
Reversed linked list(Iterative appraoch)
[145 148 145 141 141 135 142  ]

=================================