剑指offer刷题2——链表1(简单)

剑指 Offer 06. 从尾到头打印链表

难度 简单

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

示例 1:

1
2
输入:head = [1,3,2]
输出:[2,3,1]

限制:

1
0 <= 链表长度 <= 10000

通过次数277,964

提交次数369,505

思路

辅助栈法:

遍历整个链表,把所有元素压入堆栈中,最后把堆栈中的元素顺序弹出并存储到 Vector 容器中返回

算法流程: 入栈: 遍历链表,将各节点值 push 入栈。

出栈: 将各节点值 pop 出栈,存储于Vector并返回。

代码

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
int top,i,tmp;
stack<int> sta;
ListNode* P = head;
vector<int> Val;
while(P)
{
sta.push( P->val );
P = P->next;
}
while(!sta.empty())
{
Val.push_back(sta.top());
sta.pop();
}
return Val;
}
};

递归法:

利用递归: 先走至链表末端,回溯时依次将节点值加入列表 ,这样就可以实现链表值的倒序输出。

递推阶段: 每次传入 head->next ,以 head == null(即走过链表尾部节点)为递归终止条件,此时直接返回。 回溯阶段: 层层回溯时,将当前节点值加入列表,最后返回即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
if(!head)
return {};
vector<int> V = reversePrint(head->next);
V.push_back(head->val);
return V;
}
};