Given a linked list, print reverse of it using a recursive function. For example, if the given linked list is 1->2->3->4, then output should be 4->3->2->1.
Note that the question is only about printing the reverse. To reverse the list itself see this
Difficulty Level: Rookie
Algorithm:
printReverse(head) 1. call print reverse for head->next 2. print head->data
Implementation:
Javascript
<script> // Javascript program to print reverse // of a linked list // Head of list var head; // Linked list Node class Node { constructor(val) { this .data = val; this .next = null ; } } // Function to print reverse of // linked list function printReverse(head) { if (head == null ) return ; // Print list of head node printReverse(head.next); // After everything else is printed document.write(head.data + " " ); } // Utility Functions // Inserts a new Node at front of the list. function push(new_data) { /* 1 & 2: Allocate the Node & Put in the data */ new_node = new Node(new_data); // 3. Make next of new Node as head */ new_node.next = head; // 4. Move the head to point to new Node */ head = new_node; } // Driver code // Create linked list 1->2->3->4 push(4); push(3); push(2); push(1); printReverse(head); // This code is contributed by Rajput-Ji </script> |
Output:
4 3 2 1
Time Complexity: O(n)
Space Complexity: O(n) for call stack since using recursion
Please refer complete article on Print reverse of a Linked List without actually reversing for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!