Write and test a recursive Java method that reverses a singl

Write and test a recursive Java method that reverses a singly linked list so that the ordering of the nodes becomes opposite of what it was before.

Solution

// ReverseListRecursive.java
class ReverseListRecursive
{

   static Node head;

   static class Node
   {
       int key;
       Node next;

       Node(int value)
       {
           key = value;
           next = null;
       }
   }

   Node reverseLinkedList(Node currentNode, Node previousNode)
   {

       if (currentNode.next == null)
       {
           head = currentNode;

           currentNode.next = previousNode;
           return null;
       }

       Node nextNode = currentNode.next;

       currentNode.next = previousNode;

       // recursive call
       reverseLinkedList(nextNode, currentNode);
       return head;
   }

   void displayList(Node head)
   {
       while (head.next != null)
       {
           System.out.print(head.key + \"->\");
           head = head.next;
       }
       System.out.println(head.key);
   }

   public static void main(String[] args)
   {
       ReverseListRecursive linkedList = new ReverseListRecursive();
       linkedList.head = new Node(5);
       linkedList.head.next = new Node(3);
       linkedList.head.next.next = new Node(8);
       linkedList.head.next.next.next = new Node(1);
       linkedList.head.next.next.next.next = new Node(15);
       linkedList.head.next.next.next.next.next = new Node(26);
       linkedList.head.next.next.next.next.next.next = new Node(17);
       linkedList.head.next.next.next.next.next.next.next = new Node(80);
       linkedList.head.next.next.next.next.next.next.next.next = new Node(19);
       linkedList.head.next.next.next.next.next.next.next.next.next = new Node(68);
       linkedList.head.next.next.next.next.next.next.next.next.next.next = new Node(18);
       linkedList.head.next.next.next.next.next.next.next.next.next.next.next = new Node(22);
       linkedList.head.next.next.next.next.next.next.next.next.next.next.next.next= new Node(43);
       linkedList.head.next.next.next.next.next.next.next.next.next.next.next.next.next = new Node(11);

       System.out.print(\"Input List: \");
       linkedList.displayList(head);
       Node reeverse = linkedList.reverseLinkedList(head, null);
       System.out.println(\"\ \");
       System.out.print(\"Reversed List \");
       linkedList.displayList(reeverse);
   }
}

/*
output:

Input List: 5->3->8->1->15->26->17->80->19->68->18->22->43->11

Reversed List 11->43->22->18->68->19->80->17->26->15->1->8->3->5

*/