Tolani Jaiye-Tikolo Tolani Jaiye-Tikolo - 22 days ago 10
C++ Question

print Linked List elements using recursion

I was solving the Print in reverse challenge on Hackerrank


The
void ReversePrint(Node* head)
method takes one argument - the head of the linked list. You should NOT read
any input from stdin/console. The head may be empty so nothing should be printed. Print the elements of the linked list in reverse order to
stdout/console (using printf or cout) , one per line.

Sample Input

1 --> 2 --> NULL

2 --> 1 --> 4 --> 5 --> NULL

Sample Output

2
1
5
4
1
2



I solved it using this

#include <vector>
void ReversePrint(Node *head)
{
// This is a "method-only" submission.
// You only need to complete this method.

std::vector<int> nodeList;
if(head != NULL){

while(head != NULL){
nodeList.push_back(head->data);
head = head->next;
}

for (std::vector<int>::iterator it = nodeList.end()-1 ; it != nodeList.begin()-1; --it){
std::cout << *it <<endl;
}
}

}


It works perfectly but extending to use recursion provides the wrong answer, why is this happening?

std::vector<int> nodeList;
void ReversePrint(Node *head){
if(head != NULL){
nodeList.push_back(head->data);
ReversePrint(head->next);
}
else{
for (std::vector<int>::iterator it = nodeList.end()-1 ; it != nodeList.begin()-1; --it){
std::cout << *it <<endl;
}

}

}


the result is

2
1
5
4
1
2
2
1


NB: The structure of the Node is given as
struct Node
{
int data;
struct Node *next;
}

Answer

Why so complicated?

/* Function to reverse print the linked list */
void ReversePrint(Node* head)
{
    // Base case  
    if (head == NULL)
       return;

    // print the list after head node
    ReversePrint(head->next);

    // After everything else is printed, print head
    std::cout << head->data << '\n';
}