implement a function to print a list from its tail to head-interview question

 implement a function to print a list from its tail to head-interview question.

When meeting this question, many candidates' intuition is to reverse links between all nodes and to reverse the direction of a list. It fulfills the requirement if all nodes in the reversed list are printed from head to tail. However, it has to modify the structure of the input list. Is it OK to do so? It depends on the requirement in an interviewers’ minds. You should ask your interviewers to clarify their requirement before you describe your solution.

Usually, printing is a read-only operation, and it is not allowed to modify the content to be printed. Supposing interviewers disallow to reverse the direction of lists here.Nodes in a list are linked from the head to the tail, but the printing order is from the tail to the head. That is to say, the first node in the list is the last one to be printed, and the last node is the first one to be printed. It is typical “Last In, First Out,” so a stack can help to solve this problem. Every node is pushed into a stack when it is visited. After all nodes are visited and pushed into the stack, they are printed from the top of the stack and popped one by one. The printing order is opposite to the order in the list.

The sample code in bellow is based on stack in the C++ standard template library. 
C++ Code to Print a List Reversely (Iterative Version)

void PrintListReversingly_Iteratively(ListNode* pHead) {
    std::stack<ListNode*> nodes;
    ListNode* pNode = pHead;
    while(pNode != NULL) {

        nodes.push(pNode);

        pNode = pNode->m_pNext;
    }

    while(!nodes.empty()) {
        pNode = nodes.top();
        printf("%d\t", pNode->m_nValue);
        nodes.pop();

} }
It can be solved with a stack and since recursion is essentially equivalent to stacks, so it can also be solved recursively. To print a list in reverse, the next nodes are printed first when a node is visited, and then the currently visited node is printed. The recursive code is shown in bellow
 C++ Code to Print a List Reversely (Recursive Version)

void PrintListReversingly_Recursively(ListNode* pHead) {
    if(pHead != NULL) {

        if (pHead->m_pNext != NULL) {
            PrintListReversingly_Recursively(pHead->m_pNext);

}

        printf("%d\t", pHead->m_nValue);
    }

}
The previous recursive code looks more concise, but it has a limitation: the recursive calls may have too many levels to cause call stack overflow errors when the list is very long. The iterative solution with an explicit stack is more robust. More discussion about recursion and iteration are available in the section Recursion and Iteration.
Test Cases:

• Lists with multiple nodes or only one node
  
• The head node of a list is NULL
  www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community