题目描述
- 输入一个链表的头结点，从尾到头反过来打印出每个节点的值。
思路解读
代码
// 递归实现方式一
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> result;
if(head == NULL){
return result;
}
core(result, head);
return result;
}
void core(vector<int>& result, ListNode* temp){
if (temp->next != NULL){
core(result ,temp->next);
}
result.push_back(temp->val);
}
};
// 递归实现方式二
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> result;
core(result, head);
return result;
}
void core(vector<int>& result, ListNode* temp){
if (temp != NULL){
core(result ,temp->next);
result.push_back(temp->val);
}
}
};
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> result;
stack<int> sk;
while(head){
sk.push(head->val);
head = head -> next;
}
while(!sk.empty()){
result.push_back(sk.top()); // 取出栈顶数据
sk.pop(); // 删除栈顶数据
}
return result;
}
};
我是分割线，上面部分是第二轮的代码，比较简洁易懂，下面代码是第一轮写的代码，看着比较繁琐，代码不简洁，予以保留，为了见证自己的成长。节省时间的话，只看分割线上面的就好。
代码
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> obj;
int temp[1000], length = 0, i;
while(head != NULL){
temp[length++] = head->val;
head = head->next;
}
for(i = length-1; i >= 0; i--){
obj.push_back(temp[i]);
}
return obj;
}
};
总结展望
- 在牛客提交的时候，认为自己思路对，但是一直出错，后来在本地跑代码发现，是因为自己把while错用为if,导致出错，以后注意吧，不能因小失大.
- 剑指Offer 这本书不错，思路开阔.
附录
思路一: 新建一个数组，将链表中的值先依次存入数组中，然后再反向存入vector中
#include<iostream>
#include<vector>
using namespace std;
struct ListNode{
int val;
struct ListNode *next;
};
vector<int> aa(ListNode *head){
vector<int> bb;
int temp[100], length = 0;
int i;
ListNode *p;
p = head;
while(p != NULL){
temp[length++] = p->val;
p = p->next;
}
for(i=length-1; i>=0; i--){
// cout<<temp[i]<<" ";
bb.push_back(temp[i]);
}
return bb;
}
int main(){
ListNode *head, *tail, *p;
int i;
vector<int> obj;
head = tail = NULL;
for(i = 0; i < 10; i++){
p = new ListNode;
p->val = i;
if(head == NULL){
head = p;
}
else{
tail->next = p;
}
tail = p;
}
p = head;
while(p != NULL){
cout<<p->val<<" ";
p = p -> next;
}
obj = aa(head);
if(obj.empty()){
cout<<"链表为空";
}
else{
for(i = 0; i < obj.size(); i++){
cout<<obj[i]<<",";
}
}
cout<<endl;
}
思路二: 用栈来实现，因为栈是先进后出的数据结构
#include<iostream>
#include<stack>
using namespace std;
struct ListNode{
int val;
struct ListNode *next;
};
void aa(ListNode *head){
stack<ListNode *> node;
ListNode *p;
p = head;
while(p != NULL){
node.push(p); //在栈顶增加元素
p = p->next;
}
while(!node.empty()){
p = node.top(); //返回栈顶元素
cout<<p->val<<" ";
node.pop(); //移除栈顶元素
}
cout<<endl;
}
int main(){
ListNode *head, *tail, *p;
int i;
head = tail = NULL;
for(i = 0; i < 10; i++){
p = new ListNode;
p->val = i;
if(head == NULL){
head = p;
}
else{
tail->next = p;
}
tail = p;
}
aa(head);
}
思路三: 递归实现
#include<iostream>
using namespace std;
struct ListNode{
int val;
struct ListNode *next;
};
void aa(ListNode *head){
if(head != NULL){
aa(head->next);
cout<<head->val<<" ";
}
}
int main(){
ListNode *head, *tail, *p;
int i;
head = tail = NULL;
for(i = 0; i < 10; i++){
p = new ListNode;
p->val = i;
if(head == NULL){
head = p;
}
else{
tail->next = p;
}
tail = p;
}
aa(head);
}
