輸入一個鏈表的頭結(jié)點逆趣，從尾到頭打印出每個結(jié)點的值
#include <stdio.h>
#include <stack>
#include "list.h"
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();
}
}
//既然想到用棧來實現(xiàn)，而遞歸本質(zhì)就是一個棧結(jié)構(gòu)仗阅，于是可以
//先遞歸輸出它后面的結(jié)點靴姿，再輸出該結(jié)點携丁，這樣鏈表的輸出結(jié)構(gòu)就反過來了
//缺點是鏈表比較長時瘩扼，函數(shù)調(diào)用的層級很深奴拦，有可能導(dǎo)致函數(shù)調(diào)用棧溢出
void PrintListReversingly_Recursively(ListNode* pHead)
{
if(pHead != NULL)
{
if(pHead->m_pNext != NULL)
{
PrintListReversingly_Recursively(pHead->m_pNext);
}
printf("%d\t", pHead->m_nValue);
}
}
void Test(ListNode* pHead)
{
PrintList(pHead);
PrintListReversingly_Iteratively(pHead);
printf("\n");
PrintListReversingly_Recursively(pHead);
}
// 1->2->3->4->5
void Test1()
{
printf("\nTest1 begins.\n");
ListNode* pNode1 = CreateListNode(1);
ListNode* pNode2 = CreateListNode(2);
ListNode* pNode3 = CreateListNode(3);
ListNode* pNode4 = CreateListNode(4);
ListNode* pNode5 = CreateListNode(5);
ConnectListNodes(pNode1, pNode2);
ConnectListNodes(pNode2, pNode3);
ConnectListNodes(pNode3, pNode4);
ConnectListNodes(pNode4, pNode5);
Test(pNode1);
DestroyList(pNode1);
}
// 只有一個結(jié)點的鏈表: 1
void Test2()
{
printf("\nTest2 begins.\n");
ListNode* pNode1 = CreateListNode(1);
Test(pNode1);
DestroyList(pNode1);
}
// 空鏈表
void Test3()
{
printf("\nTest3 begins.\n");
Test(NULL);
}
int main(void)
{
Test1();
Test2();
Test3();
return 0;
}
結(jié)果
QQ截圖20160626220946.png
