Reverse a singly linked list in a recursive manner

This one has been an interview favourite for quite some time now. The trick is to break the operation into smaller operations and extract the common logic. In such a case it makes sense to go till the last 2 nodes and begin the reversal there. We call the method with the node in question and its previous node so that when we identify that the node which we are trying to reverse, we point it's next to the previous node and then go back doing this again and again.


In the end our head would be changed so take care that you store the new value of head and use it for any further operations.

public class LinkedList {
 class Node {
  int value;
  Node next;
  public Node(int x) {
   value = x;
  }
 }
 Node head;

 public void insertAtEnd(Node n) {
  if (head == null) {
   head = n;
  } else {
   Node i = head;
   while (i.next != null) {
    i = i.next;
   }
   i.next = n;
  }
 }

 public Node reverse(Node n, Node prev) {
  if (n == null) {
   return n;
  }
  if (n.next == null) {
   n.next = prev;
   return n;
  }
  Node x = reverse(n.next, n);
  n.next = prev;
  return x;
 }
 public static void main(String[] args) {
  LinkedList linkedList = new LinkedList();
  linkedList.insertAtEnd(linkedList.new Node(2));
  linkedList.insertAtEnd(linkedList.new Node(3));
  linkedList.insertAtEnd(linkedList.new Node(1));
  linkedList.insertAtEnd(linkedList.new Node(6));
  System.out.println("list before reversal " + linkedList);
  linkedList.head = linkedList.reverse(linkedList.head, null);
  System.out.println("list after reversal " + linkedList);
 }
}

Output is

list before reversal 2,3,1,6
list after reversal 6,1,3,2

 

Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself