剑指 Offer 06. 从尾到头打印链表

题目：

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]
 

限制：

0 <= 链表长度 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

最近比较闲，寻思再走一遍剑指。这题是个简单题，一般人想法就是遍历一遍list存入vector，再reverse vector；或者就地reverse list，再存入vector；再或者存入stack再pop出来，这些其实差别都不大。写了最简单的一版即代码1。之后在看别人的答案时，看到了一版厉害的递归，放到代码2了。确实这题在数据量不大的情况下递归很清楚，不过一般不太会想到。这里base case就是head为空，直接返回一个空的vector，然后我们每次获得的vector都是下一层递归返回的，因为要倒序，我们在下一层返回以后再将当前层的val放进vector的末端，这样就返回的vector就是倒序了。

代码1：

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    vector<int> reversePrint(ListNode* head) {

        vector<int> record;

        while (head) {

            record.push_back(head->val);

            head = head->next;

        }

        reverse(record.begin(), record.end());

        return record;

    }

};

代码2：