從尾到頭列印鏈表

02-12

從尾到頭列印鏈表

輸入一個鏈表的頭節點，從尾到頭反過來列印出每一個節點的值。鏈表的結構如下：

struct ListNode{ int m_nKey; ListNode* m_pNext;}

思路：從頭到尾遍歷整個鏈表，將節點存入棧中，最後依次出棧。

參考答案：

#include <iostream>#include <stack>using namespace std;struct ListNode{ int m_nKey; ListNode* m_pNext;};void printListRev(ListNode* pHead){stack<ListNode*> nodes;ListNode* pNode = pHead;while(pNode != NULL){ nodes.push(pNode); pNode = pNode->m_pNext;}while(!nodes.empty()){ pNode = nodes.top(); cout<<pNode->m_nKey<< ; nodes.pop();}cout<<endl;}int main(){ListNode* head = NULL;for(int i=10;i>0;i--){ ListNode* p = new ListNode; p->m_nKey = i; p->m_pNext = head; head = p;}ListNode* pNode = head;for(int i=0;i<10;i++){ cout<<pNode->m_nKey<< ; pNode = pNode->m_pNext;}cout<<endl;printListRev(head);return 0;}

思路:要實現反過來輸出鏈表,我們訪問到一個節點的時候,先遞歸輸出它後面的節點,再輸出該節點本身,

這樣鏈表的輸出就反過來了

參考代碼:

#include <iostream>#include <stack>using namespace std;struct ListNode{ int m_nKey; ListNode* m_pNext;};void printListRev(ListNode* pHead){ if(pHead != NULL) { if(pHead->m_pNext != NULL) { printListRev(pHead->m_pNext); } cout<<pHead->m_nKey<< ; }}int main(){ListNode* head = NULL;for(int i=10;i>0;i--){ ListNode* p = new ListNode; p->m_nKey = i; p->m_pNext = head; head = p;}ListNode* pNode = head;for(int i=0;i<10;i++){ cout<<pNode->m_nKey<< ; pNode = pNode->m_pNext;}cout<<endl;printListRev(head);cout<<endl;return 0;}