Repository: TheAlgorithms/Java
Pull request #4292 (2023-08-09 20:45:21)

Recursive Reverse of Linked List
<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.


BamaCharanChhandogi: @siriak could you check?

Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/lists/SinglyLinkedList.java b/src/main/java/com/thealgorithms/datastructures/lists/SinglyLinkedList.java
index 68b0fd54..f74f74fc 100644
--- 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 class SinglyLinkedList extends Node {
     }
 
     /**
-     * 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 class SinglyLinkedList extends 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


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/lists/SinglyLinkedListTest.java b/src/test/java/com/thealgorithms/datastructures/lists/SinglyLinkedListTest.java
index 57eedb97..e7c20071 100644
--- a/src/test/java/com/thealgorithms/datastructures/lists/SinglyLinkedListTest.java
+++ b/src/test/java/com/thealgorithms/datastructures/lists/SinglyLinkedListTest.java
@@ -108,7 +108,7 @@ public class SinglyLinkedListTest {
 
         // 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 @@ public class SinglyLinkedListTest {
         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 @@ public class SinglyLinkedListTest {
 
         // 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 @@ public class SinglyLinkedListTest {
             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--;
+        }
+    }
 }
\ No newline at end of file