Redirecting to
NADOS

Reverse Linked List (pointer - Recursive)

  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 reversePR and reversePRHelper functions. The functions are expected to reverse the linked list by using recursion and changing the "next" data member of nodes.
3. Input and Output is managed for you. 

Note -> The online judge can't force you to write recursive function, nor can it check if you changed the "next" data member or not. 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 
200 11 10 9 8 7 6 5 4 3 2 1 100


  • Editorial

    The problem deals with displaying the reversed linked list recursively with the help of pointers, in other words, we need to direct the node pointers to develop the reversed list.

    The only way to reverse the list using pointers is to point the node next to the current node to the current node. Here we will also use this approach but recursively. For that, we traverse our list to the end, and then for every function return, we point the next node to the current node. Recursion here ensures that we do not lose any data and our data remains unchanged.

    To sum, all we need to do here is to apply recursion to traverse the list, and while returning ensure that we point the next node to the current node. Now after this, the head node needs to be tackled separately as there is no node behind it where it would point so we need to point it to null. Now all that is left is to update the data member linked list with the reversed list.

    Below is the implementation in Java: 

    private void reversePRHelper(Node node) {
                                    if (node == tail) {
                                    return;
                                    }
                                    reversePRHelper(node.next);
                                    node.next.next = node;
                                } 
                                public void reversePR() {
                                    reversePRHelper(head);
                                    Node temp = head;
                                    head = tail;
                                    tail = temp;
                                    tail.next = null;
                                }

    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