What makes it print the linked list in reverse order?-CodePudding

struct Node
{
 int data;
 Node *next;
};
void myLinkedList( Node* navigatePtr )
{
 if(navigatePtr == NULL)
 return;
 myLinkedList(navigatePtr -> next);
 cout << navigatePtr -> data << " ";
}
int main()
{
 // Assuming that head is a pointer pointing to
 // a linked list 1 -> 2 -> 3 -> 4 -> 5
 myLinkedList(head);
 return 0;
}

This is a question from a past year paper. It asks for the output which is 5,4,3,2,1. But, i do not understand what makes it print the linked list in reverse.

CodePudding user response：

Because that is the order you asked for

myLinkedList(navigatePtr -> next);
cout << navigatePtr -> data << " ";

Try swapping those two around to get the right order

cout << navigatePtr -> data << " ";
myLinkedList(navigatePtr -> next);

Your version prints the rest of the list first, followed by the current item, reverse order in other words.

BTW the correct version, where the recursive call is the very last thing that happens in the function is called tail recursion. Tail recursion can always be replaced by a simple while loop. That's probably what you should do here (unless you are just practising recursion).

CodePudding user response：

Translated into English: "first print the rest of the list, then print this element".

So, to print [1->2->3], you must first print [2->3] and then 1, and in order to do that, you must first print [3] and then 2, and in order to that, you must first print the empty list and then 3.

Printing the empty list does nothing, then you print 3, then 2, and then 1.