题目描述

• 输入一个链表的头结点，从尾到头反过来打印出每个节点的值。

思路解读

• 剑指Offer 58

代码

• 思路一 递归实现的两种路线，仔细体会哦。

// 递归实现方式一
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);
}