從尾到頭打印鏈表

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

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