【剑指Offer】从尾到头打印链表

题目描述

输入一个链表,按链表值从尾到头的顺序返回一个ArrayList

算法分析

  1. 使用递归的方法:

    我们可以使用递归函数,headhead->next存在的时候进入下一层,当进入最后一层的时候开始从尾部返回。

  2. 使用栈的方法:

    首先遍历一遍链表,将顺序的值压栈,然后利用栈的性质(后进先出)进行打印。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/

// 递归
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> result;
helper(head, result);
return result;
}

private:
void helper(ListNode* head, vector<int> &result){
if(head){
if(head -> next){
helper(head -> next, result);
}
result.push_back(head -> val);
}
}
};


// 栈
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> res;
stack<int> st;

while (head) {
st.push(head->val);
head = head->next;
}

while (!st.empty()) {
res.push_back(st.top());
st.pop();
}

return res;
}
};