本文为剑指 offer 系列第五篇。
题目要求就是打印链表，属于很常见的问题，但是因为题目要求从尾到头打印链表，所以又生出了一些波折。
输入一个链表，按链表从尾到头的顺序返回一个ArrayList.
解题思路
思路1
从头到尾遍历这个链表，然后将得到的值插入用于保存结果的vector的初始位置。
这个方法很容易能够想到，但是性能其实不是很好，就是因为在vector开头插入元素的时候，需要将这个vector中的所有元素向后移动一位，所以复杂度就会比较高，更多详细的解释可以看之后的关于字符串替换的那个题目。
思路2
从头到尾遍历这个链表，将遍历得到的值依次插入到用于保存结果的vector的后面，最后再反转整个vector。
思路3
从头到尾遍历这个链表，将数据压入到对应的栈中，然后利用栈的先进后出的特性，将所有结果出栈，以后插入用于保存结果的vector后面即可。
解题代码
思路1代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| /**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
// 思路1: 遍历的时候前面插入结果
vector<int> res;
ListNode *p = head;
while(p){
res.insert(res.begin(),p->val);
p = p->next;
}
return res;
}
};
|
时间复杂度为O(n^2),空间复杂度为O(n)
思路2代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
// 思路2: 遍历的时候后插，然后返回reverse的结果。 4ms 480k
vector<int> res;
ListNode* p = head;
while(p){
res.push_back(p->val);
p = p->next;
}
reverse(res.begin(),res.end());
return res;
}
};
|
时间复杂度为O(n),空间复杂度为O(n)
思路3代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
// 思路3: 通过栈先进后出的特性来实现链表的从尾到头遍历 3ms 460k
vector<int> res;
ListNode* p = head;
stack<int> mstack;
while(p){
mstack.push(p->val);
p = p->next;
}
while(mstack.size() != 0){
res.push_back(mstack.top());
mstack.pop();
}
return res;
}
};
|
时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！