CODEWITHSUNDEEP
c++recursiondata-structureslinked-list
Tolani
Tolani

Reputation: 609

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

Upvotes: 0

Views: 2633

Answers (3)

Ramkumar lodhi
Ramkumar lodhi

Reputation: 131

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

Upvotes: 0

Bhagwati Malav
Bhagwati Malav

Reputation: 3549

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

Upvotes: 0

GorvGoyl
GorvGoyl

Reputation: 49640

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

Upvotes: 6

Related Questions