Redirecting to
NADOS

Display Reverse (recursive) - Linked List

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a partially written LinkedList class.
2. You are required to complete the body of displayReverse and displayReverseHelper functions. The function are expected to print in reverse the linked list without actually reversing it. 
3. Input and Output is managed for you. 

Note -> The online judge can't force you to write recursive function. But that is what the expectation is, the intention in to help you learn.
Input Format 
Input is managed for you
Output Format 
Output is managed for you
Question Video
Constraints 
1. Time complexity -> O(n)
2. Space complexity -> O(n)
Sample Input 
11
1 2 3 4 5 6 7 8 9 10 11
100
200
Sample Output 
1 2 3 4 5 6 7 8 9 10 11 
11 10 9 8 7 6 5 4 3 2 1 
200 1 2 3 4 5 6 7 8 9 10 11 100


  • Editorial

    The problem deals with displaying the reversed linked list, recursively this time. In earlier problems, we developed an iterative solution but here we will come up with a recursive approach. The idea is simple where we just need to traverse the list till the end using recursion and after we hit the base case and start returning the function calls in recursion stack, then at that point we will print the corresponding element. This is similar to the print decreasing problem we discussed in recursion level 1.

    Recursion Flow:

    Below is the implementation in Java: 

    private void displayReverseHelper(Node node) {
                                    if (node == null) {
                                    return;
                                    }
                                    displayReverseHelper(node.next);
                                    System.out.print(node.data + " ");
                                } 
                                public void displayReverse() {
                                    displayReverseHelper(head);
                                    System.out.println();
                                }

    java false

    Time Complexity: O(n)

    The time complexity for the function is linear as we are traversing on every node.

    Space Complexity: O(n)

    The space complexity for the function is linear as we have n function calls hence we have consumed a linear space in the recursion stack.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name