Add Recursive Reverse of Linked List (TheAlgorithms#4292)

BamaCharanChhandogi · BamaCharanChhandogi · web-flow · commit 4fe419ebd894 · 2023-08-10T11:38:56.000+03:00
Co-authored-by: BamaCharanChhandogi &lt;b.c.chhandogi@gmailcom&gt;
diff --git a/src/main/java/com/thealgorithms/datastructures/lists/SinglyLinkedList.java b/src/main/java/com/thealgorithms/datastructures/lists/SinglyLinkedList.java
@@ -119,10 +119,10 @@ public void swapNodes(int valueFirst, int valueSecond) {
     }
 
     /**
-     * Reverse a singly linked list from a given node till the end
+     * Reverse a singly linked list[Iterative] from a given node till the end
      *
      */
-    public Node reverseList(Node node) {
+    public Node reverseListIter(Node node) {
         Node prev = null;
         Node curr = node;
 
@@ -141,6 +141,23 @@ public Node reverseList(Node node) {
         // the reversed linkedlist
         return prev;
     }
+    /**
+     * Reverse a singly linked list[Recursive] from a given node till the end
+     *
+     */
+    public Node reverseListRec(Node head) {
+        if (head == null || head.next == null) {
+            return head;
+        }
+
+        Node prev = null;
+        Node h2 = reverseListRec(head.next);
+
+        head.next.next = head;
+        head.next = prev;
+
+        return h2;
+    }
 
     /**
      * Clear all nodes in the list
diff --git a/src/test/java/com/thealgorithms/datastructures/lists/SinglyLinkedListTest.java b/src/test/java/com/thealgorithms/datastructures/lists/SinglyLinkedListTest.java
@@ -108,7 +108,7 @@ void reverseList() {
 
         // Reversing the LinkedList using reverseList() method and storing the head of the reversed
         // linkedlist in a head node The reversed linkedlist will be 4->3->2->1->null
-        Node head = list.reverseList(list.getHead());
+        Node head = list.reverseListIter(list.getHead());
 
         // Recording the Nodes after reversing the LinkedList
         Node firstNode = head; // 4
@@ -133,7 +133,7 @@ void reverseListNullPointer() {
         Node first = list.getHead();
 
         // Reversing the linkedlist
-        Node head = list.reverseList(first);
+        Node head = list.reverseListIter(first);
 
         // checking whether the method works fine if the input is null
         assertEquals(head, first);
@@ -147,7 +147,7 @@ void reverseListTest() {
 
         // Reversing the LinkedList using reverseList() method and storing the head of the reversed
         // linkedlist in a head node
-        Node head = list.reverseList(list.getHead());
+        Node head = list.reverseListIter(list.getHead());
 
         // Storing the head in a temp variable, so that we cannot loose the track of head
         Node temp = head;
@@ -160,4 +160,51 @@ void reverseListTest() {
             i--;
         }
     }
+    // This is Recursive Reverse List Test
+    // Test to check whether the method reverseListRec() works fine
+    void RecursiveReverseList() {
+        // Create a linked list: 1 -> 2 -> 3 -> 4 -> 5
+        SinglyLinkedList list = createSampleList(5);
+
+        // Reversing the linked list using reverseList() method
+        Node head = list.reverseListRec(list.getHead());
+
+        // Check if the reversed list is: 5 -> 4 -> 3 -> 2 -> 1
+        assertEquals(5, head.value);
+        assertEquals(4, head.next.value);
+        assertEquals(3, head.next.next.value);
+        assertEquals(2, head.next.next.next.value);
+        assertEquals(1, head.next.next.next.next.value);
+    }
+
+    @Test
+    void RecursiveReverseListNullPointer() {
+        // Create an empty linked list
+        SinglyLinkedList list = new SinglyLinkedList();
+        Node first = list.getHead();
+
+        // Reversing the empty linked list
+        Node head = list.reverseListRec(first);
+
+        // Check if the head remains the same (null)
+        assertNull(head);
+    }
+
+    @Test
+    void RecursiveReverseListTest() {
+        // Create a linked list with values from 1 to 20
+        SinglyLinkedList list = createSampleList(20);
+
+        // Reversing the linked list using reverseList() method
+        Node head = list.reverseListRec(list.getHead());
+
+        // Check if the reversed list has the correct values
+        int i = 20;
+        Node temp = head;
+        while (temp != null && i > 0) {
+            assertEquals(i, temp.value);
+            temp = temp.next;
+            i--;
+        }
+    }
 }
