print Linked List elements using recursion

Question

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

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

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
– WhiZTiM, Commented Nov 16, 2016 at 17:57
Ditch the global vector. The call stack is your data structure for the recursive approach. — StoryTeller - Unslander Monica
– StoryTeller - Unslander Monica, Commented Nov 16, 2016 at 17:58
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. — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Nov 16, 2016 at 17:58
I commented the first implementation while running the second. does it affect the result — Tolani
– Tolani, Commented Nov 16, 2016 at 17:59

GorvGoyl · Accepted Answer · 2016-11-16 18:09:49Z

6

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

edited Nov 16, 2016 at 18:09

answered Nov 16, 2016 at 18:06

GorvGoyl

47.2k37 gold badges268 silver badges267 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Bhagwati Malav · Accepted Answer · 2016-11-18 02:33:52Z

0

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

answered Nov 18, 2016 at 2:33

Bhagwati Malav

3,5592 gold badges22 silver badges35 bronze badges

Comments

Ramkumar lodhi · Accepted Answer · 2019-10-09 10:39:16Z

0

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

answered Oct 9, 2019 at 10:39

Ramkumar lodhi

1316 bronze badges

Collectives™ on Stack Overflow

print Linked List elements using recursion

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related