題目：

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

鏈表結點定義：

struct ListNode{int value;ListNode* pNext; };

思路：

1、改變鏈表結構的話，先反轉鏈表，然后從頭到尾打印每個結點的值。（后續博文會有相關實現，這里就暫不實現）

2、無需改變鏈表結構，使用棧，遍歷整個鏈表，將結點依次入棧，然后再依次出棧，實現“后進先出”。

3、無需改變鏈表結構，遞歸實現,如果鏈表結點數過多的話，可能會導致棧溢出。

代碼：

void PrintListReversingly_Iteratively(ListNode* pHead){std::stack<ListNode*> nodes;ListNode* pNode=pHead;while(pNode!=NULL){nodes.push(pNode);pNode=pNode->pNext;}while(!nodes.empty()){pNode=nodes.top();cout<<pNode->value<<"\t";nodes.pop();}cout<<endl; }void PrintListReversingly_Recursively_1(ListNode* pHead){if(pHead==NULL)return;PrintListReversingly_Recursively_1(pHead->pNext);cout<<pHead->value<<"\t"; }void PrintListReversingly_Recursively_2(ListNode* pHead){if(pHead!=NULL){if(pHead->pNext!=NULL)PrintListReversingly_Recursively_2(pHead->pNext);cout<<pHead->value<<"\t";} }

在線測試OJ：

http://www.nowcoder.com/books/coding-interviews/d0267f7f55b3412ba93bd35cfa8e8035?rp=1

AC代碼：

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ class Solution { public:void printList(ListNode* head,vector<int> &nodes){if(head!=NULL){printList(head->next,nodes);nodes.push_back(head->val);}return;}vector<int> printListFromTailToHead(struct ListNode* head) {vector<int> nodes;printList(head,nodes);return nodes;} }; /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ class Solution { public:vector<int> printListFromTailToHead(struct ListNode* head) {vector<int> nodes;while(head!=NULL){nodes.push_back(head->val);head=head->next;}reverse(nodes.begin(),nodes.end());return nodes;} };

　　

轉載于:https://www.cnblogs.com/AndyJee/p/4624417.html

總結

以上是生活随笔為你收集整理的（剑指Offer）面试题5：从尾到头打印链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。