#include <iostream>
#include <stack>

struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
};

void PrintListReversingly_Recursively_01(ListNode * pHead) {
    std::stack<ListNode *> nodes;
    // 使用stack的先进后出来实现
    ListNode * pNode = pHead;
    while (pNode != NULL) {
        nodes.push(pNode);
        pNode = pNode->m_pNext;
    }
    
    while (!nodes.empty()) {
        pNode = nodes.top();
        printf("%d \t ",pNode->m_nKey);
        nodes.pop();
    }
}

void PrintListReversingly_Recursively(ListNode* pHeader) {
    if (pHeader != NULL) {
        if (pHeader->m_pNext != NULL) {
            PrintListReversingly_Recursively(pHeader->m_pNext);//使用递归
        }
        printf("%d \t ",pHeader->m_nKey);
    }
}

int main() {
    ListNode * node1 = new ListNode();
    ListNode * node2 = new ListNode();
    ListNode * node3 = new ListNode();
    
    node1->m_nKey = 1;
    node1->m_pNext = node2;
    
    node2->m_nKey = 2;
    node2->m_pNext = node3;
    
    node3->m_nKey = 3;
    node3->m_pNext = NULL;
    
    PrintListReversingly_Recursively(node1);
    
    printf("\n");//换行
    
    PrintListReversingly_Recursively(node1);
    
    delete node1;
    delete node2;
    delete node3;
    return 0;
}