剑指offer-从尾到头打印链表

悠悠 2022-04-24 03:00 163阅读 0赞

##### 题目描述 #####

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

##### 实现思想 #####

用递归的办法很容易实现。  
如果还没有到列表的尾部，就递归，当退出函数的时候将当前列表的值添加到vector中就可以了。

##### 实现代码 #####

#include <stdc++.h>
    
    using namespace std;
    
    
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
                val(x), next(NULL) {
        }
    };
    
    class Solution {
    public:
        vector<int> printListFromTailToHead(ListNode* head) {
            vector<int> vec;
            if(head == NULL) //①处如果缺少了这个判断条件，出现的情况见总结
                return vec;
            helper(vec, head);
            return vec;
        }
        void helper(vector<int> &vec, ListNode *head) {
            if(head->next != NULL)
                helper(vec, head->next);
            vec.push_back(head->val);
    
        }
    };
    
    int main()
    {
        ListNode *p_head = new ListNode(0);
        ListNode *p = p_head;
        for(int i = 0; i < 9; i++) {
            ListNode *p_n = new ListNode(0);
            p->next = p_n;
            p = p->next;
            p->val = i + 1;
            cout << p->val;
        }
        cout << endl;
        Solution S;
        vector<int> vec;
        vec = S.printListFromTailToHead(p_head);
        for(vector<int>::iterator it = vec.begin(); it < vec.end(); it++)
            cout << *it;
    
    
        return 0;
    }

##### 运行截图 #####

![在这里插入图片描述][20190411213208684.png]

##### 总结 #####

1.  main函数中结构体变量的定义方式为`ListNode *p_head = new ListNode(0);`必须加上new关键字。作者在写的时候就忘记了new关键字一直出现报错。
2.  `vector<int>::iterator it = vec.begin(); it < vec.end(); it++`  
    用迭代器的办法访问向量vector，访问迭代器的值用\*it
3.  **重点**：当缺少了上述代码中的①处判断条件，在编译器中是可以运行通过的，但是在牛客网上运行不通过，提示 “您的代码已保存 段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起 case通过率为0.00%”  
    因为编译器中运行的时候输入的测试用例的情况较少，没有考虑到链表为空的情况，所以没有报错，牛客网的测试用例有到这种情况，所以出现case通过率为0.00%。（提示广大程序员，如果牛客网出现这个提示，都是测试用例没考虑完全！）

[20190411213208684.png]: /images/20220221/49828acd2284435683a5e0ffa8f9667d.png