從尾到頭打印鏈表

信息卡片

• 時間：2020-03-23
• 題目：從尾到頭打印鏈表
• tag：list

題目描述

輸入一個鏈表，按鏈表從尾到頭的順序返回一個 ArrayList。

---

01

調用 reverse 函數

解題思路

這是一種簡單粗暴的解法。先遍歷一遍鏈表，在遍歷鏈表的同時將當前指針指向的值放入 vector 數組中，直到鏈表遍歷完成。最后，使用 reverse 函數將 vector 數組進行反轉。

public:vector<int> printListFromTailToHead(ListNode* head) {vector<int>ArrayList;if(!head || !head->next)return {};while(head){ArrayList.push_back(head->val);head=head->next;}reverse(ArrayList.begin(),ArrayList.end());return ArrayList;} };

02

調用 insert 函數

解題思路

與解法一有些類似，依次從前往后遍歷鏈表，在遍歷鏈表的同時，調用 vector 的 insert 函數從頭部插入此時鏈表指針指向的值。最后就得到了一個反轉的數組。

class Solution { public:vector<int> printListFromTailToHead(ListNode* head) {vector<int>ArrayList;if(head){ArrayList.insert(ArrayList.begin(),head->val);while(head->next){ArrayList.insert(ArrayList.begin(),head->next->val);head=head->next;}}return ArrayList;} };

03

調用棧方法

解題思路

創建一個元素為指針類型的棧，來存放鏈表的指針。在遍歷鏈表的同時將指針入棧，此時棧的底部是鏈表的第一個元素，棧頂是鏈表的最后一個元素。彈出棧的時候把指針指向的值放入 vector 數組里面。

class Solution { public:vector<int> printListFromTailToHead(ListNode* head) {stack<ListNode*> stackNodes;vector<int> ArrayList;ListNode* p=head;while (p != NULL){stackNodes.push(p);p = p->next;}while (!stackNodes.empty()){p=stackNodes.top();ArrayList.push_back(p->val);stackNodes.pop();}return ArrayList;} };

04

遞歸調用

解題思路

遞歸的本質就是一個棧結構，可以用遞歸來實現。要實現反過來輸出的鏈表，我們每訪問到一個節點的時候，先遞歸輸出它后面的節點，再輸出該節點自身，這樣就得到反轉的鏈表。

class Solution { public:vector<int> printListFromTailToHead(struct ListNode* head) {vector<int> vec;printListFromTailToHead(head,vec);return vec;}void printListFromTailToHead(struct ListNode* head,vector<int> &vec) {if(head!=nullptr){if(head->next!=nullptr){printListFromTailToHead(head->next,vec);}vec.push_back(head->val);}} };

總結

解法四遞歸的方法看起來比較簡潔，但是凡事都有利弊，當鏈表非常長的時候，就會導致函數調用的層級很深，從而有可能導致函數調用棧溢出。解法一、解法二、解法三要優于解法四。

總結

以上是生活随笔為你收集整理的链表怎么输出最后一个元素无空格_剑指offer系列----从尾到头打印链表的全部內容，希望文章能夠幫你解決所遇到的問題。

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