剑指offer-反向打印链表

题目描述

输入一个链表,从尾到头打印链表每个节点的值。

分析

从尾到头打印,第一反应是将链表的指针反序,写代码AC.

但是这种方法实际上不是很优雅,因为改动了输入.

看了答案,本质上是一个先进后出的问题,所以可以借助堆栈来实现.
当然也可以通过递归来实现.

代码

指针反序

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
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> values;
if(head==NULL){
return values;
}
if(head->next==NULL){
values.push_back(head->val);
return values;
}
ListNode* p = head;
ListNode* next_node = p->next;
ListNode* next_next_node = NULL;
while(true){
next_next_node = next_node->next;
next_node->next = p;
p = next_node;
next_node = next_next_node;
if(next_node==NULL){
break;
}
}
head->next = NULL;
while(p){
values.push_back(p->val);
p = p->next;
}
return values;
}
};

堆栈实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
stack<int> s;
vector<int> v;
while(head){
s.push(head->val);
head = head->next;
}
int len=s.size();
for(int i=0;i<len;i++){
v.push_back(s.top());
s.pop();
}
return v;
}
};