劍指offer做題記錄：06. 從尾到頭列印連結清單(C++實作，棧，遞歸，數組等含代碼）
連結：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
題目描述：
輸入一個連結清單的頭節點，從尾到頭反過來傳回每個節點的值（用數組傳回）。
示例1：
輸入：head = [1,3,2]
輸出：[2,3,1]
限制：0 <= 連結清單長度 <= 10000
思路：
- 1.使用棧操作，可以将連結清單節點值直接添加進棧再周遊添加到數組中傳回；
- 2.通過vector的reverse函數，将連結清單周遊後添加進arr數組，通過reverse(arr.begin(),arr.end());進行翻轉然後傳回；
- 3.通過vector的insert函數（慎！此方法執行耗時極大）周遊連結清單通過vector中自帶的insert函數進行每次都在頭插入新值然後傳回數組；
- 4.通過遞歸，通過實作另一份遞歸方法找到連結清單尾結點進行添加進數組，之後遞歸全部完成直接傳回即可；
- 5.通過疊代器反向周遊，首先周遊數組得到數量count，之後進行調用vector中rbegin函數反向取得元素的疊代器進行從數組尾周遊到頭依次放傳入連結表正周遊的值，傳回數組；
- 以上思路代碼實作如下所示：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
// //4.遞歸實作
// void method(vector<int>& res,ListNode* head){
// if(head==NULL) return;
// method(res,head->next);
// res.push_back(head->val);
// }
vector<int> reversePrint(ListNode* head) {
//1.通過棧操作
vector<int> arr;
stack<int> st;
ListNode* pNode = head;
while(pNode)
{
st.push(pNode->val);
pNode = pNode->next;
}
while(!st.empty())
{
arr.push_back(st.top());
st.pop();
}
return arr;
//2.通過vector的reverse函數 執行用時： 4 ms , 在所有 C++ 送出中擊敗了 87.76% 的使用者
//記憶體消耗： 8.5 MB , 在所有 C++ 送出中擊敗了 67.45% 的使用者
// vector<int> arr;
// ListNode *pNode = head;
// while(pNode)
// {
// arr.push_back(pNode->val);
// pNode = pNode->next;
// }
// reverse(arr.begin(),arr.end());
// return arr;
//3.通過vector的insert函數--不提倡 執行用時：
// 76 ms
// , 在所有 C++ 送出中擊敗了
// 6.50%
// 的使用者
// 記憶體消耗：
// 8.5 MB
// , 在所有 C++ 送出中擊敗了
// 68.32%
// 的使用者
// vector<int> arr;
// ListNode *pNode = head;
// while( pNode )
// {
// arr.insert(arr.begin(),pNode->val);
// pNode = pNode->next;
// }
// return arr;
// //4.遞歸實作
// vector<int> res;
// method(res,head);
// return res;
//5.通過疊代器周遊執行用時：
// 8 ms
// , 在所有 C++ 送出中擊敗了
// 42.89%
// 的使用者
// 記憶體消耗：
// 8.4 MB
// , 在所有 C++ 送出中擊敗了
// 79.04%
// 的使用者
// ListNode* pNode = head;
// int count = 0;
// while( pNode )
// {
// ++count;
// pNode = pNode->next;
// }
// vector<int> arr(count);
// pNode = head;
// for(auto i = arr.rbegin(); i != arr.rend(); ++i)
// {
// *i = pNode->val;
// pNode = pNode->next;
// }
// return arr ;
}
};
記錄完成OUO
此處就放個使用棧的執行結果:
(但其他方法也是好用的都測試過了，隻是懶得截圖了orz)
最後感謝觀看OVO，歡迎點贊評論，留下自己想法大家可以互相交流~