---

題目描述

輸入一個鏈表的頭節點，從尾到頭反過來返回每個節點的值（用數組返回）。

示例 1：

輸入：head = [1,3,2]
輸出：[2,3,1]

限制：

0 <= 鏈表長度 <= 10000

---

思路

只是想做出來的話，不斷用insert在vector首元素之前插入鏈表的值就好了。但是在順序容器的相關知識里說過，vector除尾后之外的位置進行插入操作都會將后面的元素全部移動一遍，代價是很大的，而題目想要返回vector，顯然不是想要直接進行首元素之前的insert操作（雖然試了試也過了。。。）

遞歸和棧兩種方法效率上并無優劣之分，時間復雜度和空間復雜度是一樣的，但是如果測試數據過大有沒有可能導致遞歸法崩潰呢？這是我一直所擔心的問題。

其實棧的先進后出思想是最契合本題的。

---

遞歸法

class Solution {
public:vector<int> vc;vector<int> reversePrint(ListNode* head) {recur(head);return vc;}void recur(ListNode* head){if(head == NULL){return;}recur(head->next);vc.push_back(head->val);}
};

時間復雜度 O(N)： 遍歷鏈表，遞歸 N 次。
空間復雜度 O(N)： 系統遞歸需要使用 O(N)的棧空間。

---

棧

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

時間復雜度 O(N)： 入棧和出棧共使用 O(N)時間。
空間復雜度 O(N)： 棧 si 和數組 vc 共使用 O(N)的額外空間。

---