從尾到頭打印鏈表

題目：輸入一個鏈表的頭結點，從尾到頭反過來打印出每個結點的值。

思路1:使用棧

思路2:遞歸

#include<iostream>
#include <stdlib.h>
#include <stack>

using namespace std;

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

ListNode* CreateListNode(int value)
{
    ListNode *pNode = new ListNode();
    pNode->m_nValue = value;
    pNode->m_pNext = NULL;
    return pNode;
}

void PrintListNode(ListNode* pNode)
{
    printf("%d\n", pNode->m_nValue);
}

//打印鏈表
void PrintList(ListNode* pHead)
{
    ListNode* pNode = pHead;
    while(pNode != NULL)
    {
        cout << pNode->m_nValue<<" ";
        pNode=pNode->m_pNext;
    }
    cout << endl;
}

//在鏈表結尾添加一個結點
void AddToTail(ListNode** pHead, int value)
{
    ListNode* pNew = new ListNode();
    pNew->m_nValue = value;
    pNew->m_pNext = NULL;

    if(*pHead == NULL)
    {
        *pHead = pNew;
    }
    else
    {
        ListNode* pNode = *pHead;
        while(pNode->m_pNext != NULL)
            pNode = pNode->m_pNext;

        pNode->m_pNext=pNew;
    }

}

//方法1: 用棧實現
void PrintListReversingly_Iteratively(ListNode* pHead)
{
    ListNode* pNode = pHead;
    stack<ListNode*> nodes;

    while(pNode != NULL)
    {
        nodes.push(pNode);
        pNode = pNode->m_pNext;
    }

    while(!nodes.empty())
    {
        pNode = nodes.top();
        cout<<pNode->m_nValue<<" ";
        nodes.pop();
    }
    cout << endl;
}

//方法2: 遞歸
void PrintListReversingly_Recursively(ListNode* pHead)
{
    ListNode* pNode = pHead;
    if(pNode != NULL)
    {
        if(pNode->m_pNext != NULL)
            PrintListReversingly_Recursively(pNode->m_pNext);
    }
    cout<<pNode->m_nValue<<" ";
}

// 1->2->3->4->5->6->7
int main()
{
    ListNode* pNode1 = CreateListNode(1);
    PrintList(pNode1);

    AddToTail(&pNode1,2);
    AddToTail(&pNode1,3);
    AddToTail(&pNode1,4);
    AddToTail(&pNode1,5);
    AddToTail(&pNode1,6);
    AddToTail(&pNode1,7);

    PrintList(pNode1);
   
    PrintListReversingly_Iteratively(pNode1);
    PrintListReversingly_Recursively(pNode1);
   
    return 0;
}