[数据结构与算法]【JZ6 从尾到头打印链表】

描述
输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。

如输入{1,2,3}的链表如下图:

返回一个数组为[3,2,1]

0 <= 链表长度 <= 10000

示例1

输入： {1,2,3}

返回值： [3,2,1]

示例2

输入： {67,0,24,58}

返回值： [58,24,0,67]

解法一 直接遍历

题目很简单，很朴素。我们直接从这个链表的头节点开始进行遍历。然后我们记录下这个数组的每个节点的信息。最后,使用std::reverse()函数反转一下整个数组，返回即可。

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> vec;
        while(head){
            vec.push_back(head->val);
            head = head->next;
        }
        reverse(vec.begin(),vec.end());
        return vec;
    }
};

运行时间：5ms
超过6.17% 用C++提交的代码
占用内存：904KB
超过19.46%用C++提交的代码

解法二 递归写法(源自官方解释)

由于这个题目需要我们从后面向前面开始打印这个数组。所以我们可以对遍历的结点进行一个递归，我们先递归到这个链表的最后面，然后不断向前收集权值

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> vec;
        if(!head) return vec;
        vec = printListFromTailToHead(head->next);
        vec.push_back(head->val);
        return vec;
    }
};

运行时间：6ms
超过3.16% 用C++提交的代码
占用内存：1920KB
超过14.07%用C++提交的代码