print Linked List elements using recursion

0
votes

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; }

3
c++recursiondata-structureslinked-list
In the result of your recursive version, I notice a repetition of the first input set after printing the second. Did you clear contents of the global vector after printing for each input set? - WhiZTiM
Ditch the global vector. The call stack is your data structure for the recursive approach. - StoryTeller - Unslander Monica
Please refrain asking questions about online code judge engines here. It's very unlikely that anyone could tell you where you failed from their test cases, as these aren't disclosed usually. Even if what you tested was running at your local environment, you may have missed to test some edge cases which are applied in the online challenge. Be creative and try to find them. Additionally there's probably no value for such questions in the long term, other than cheating the online contest, and nothing is learned. - πάντα ῥεῖ
I commented the first implementation while running the second. does it affect the result - Tolani
No. Commented code doesn't get compiled. - StoryTeller - Unslander Monica

3 Answers

6
votes

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';
}
0
votes

In case, you want to return reversed linked list:

  Node* List::reverseList()
{
    if(head == NULL) return;

    Node *prev = NULL, *current = NULL, *next = NULL;
    current = head;
    while(current != NULL){
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}
0
votes

You can reverse the linked list recursively then print the linked list.

Node* reverse(Node* node) 
{ 
    if (node == NULL) 
        return NULL; 
    if (node->next == NULL)
    { 
        head = node; 
        return node; 
    } 
    Node* temp= reverse(node->next); 
    temp->next = node; 
    node->next = NULL; 
    return node;
}