AcWing 17. 从尾到头打印链表
原题链接
简单
作者:
feel1nG
,
2024-07-22 15:41:03
,
所有人可见
,
阅读 1
// 法一:reverse 答案数组. 时间:O(n);空间:O(n). 4ms; 8.5MB
class Solution {
public:
vector<int> printListReversingly(ListNode* head) {
vector<int> res;
while (head) {
res.push_back(head->val);
head = head->next;
}
// reverse(res.begin(), res.end());
// return res;
return vector<int>(res.rbegin(), res.rend());
//同上两行效果,从尾到头遍历这个(res)动态数组,并放在一个新的动态数组里面
}
};
// 法二:递归. 时间:O(n);空间:栈空间O(n). 4ms; 10.8MB
class Solution {
public:
vector<int> printListReversingly(ListNode* head) {
if (!head) return {};
auto res = printListReversingly(head->next);
res.push_back(head->val);
return res;
}
};
// 法三:辅助栈法. 时间:O(n);空间:O(n). 4ms; 8.5MB
class Solution {
public:
vector<int> printListReversingly(ListNode* head) {
stack<int> s;
while (head) {
s.push(head->val); // 存的是 val
head = head->next;
}
int n = s.size();
vector<int> res(n);
for (int i = 0; i < n; i ++ ) {
res[i] = s.top();
s.pop();
}
return res;
}
};