题解 | #从尾到头打印链表#

题解一：递归
题解思路：使用递归先走到链表的末尾，再在回溯时将链表节点中的值加入到数组中。
递归边界： head == NULL;
递归阶段：一直传入head->next;
回溯阶段：将值加入到数组；
图示：

复杂度分析：
时间复杂度:，回溯遍历了整个链表
空间复杂度:，去掉输出最终结果vector的数组，栈递归深度为N，所以使用栈的空间为O(N)

实现如下：

class Solution {
public:
    vector<int> ans;
    void recur(ListNode* head){
        if(head == NULL)  //head == NULL表示递归结束
            return;
        recur(head->next);  
        ans.push_back(head->val);  // 回溯将链表值加入到ans
    }
    vector<int> printListFromTailToHead(ListNode* head) {
        recur(head);
        return ans;
    }
};

题解二：使用std::reverse()
解题思路： 使用vector保存链表中的，然后使用reverse()反转整个vector
复杂度分析：
时间复杂度： ，使用while循环遍历了整个链表O(n)，翻转数组时间复杂度O(n);
空间复杂度： ，去掉输出最终结果vector的数组，没有再申请其他空间了

实现如下：

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

题解三： 反转链表 （先将反转链表，再依次遍历打印值）
主要思路：
1.定义两个指针pre,cur; pre在前，cur在后； cur初始为NULL, pre初始为链表头。
2.每次让pre的next指向cur,实现一次局部反转； 之后，pre与cur同时向前移动一位。
3. 当pre为NULL表示反转完成。
4.从cur开始遍历反转之后的链表
图示：

复杂度分析：
时间复杂度：O(N),使用while循环反转整个链表O(n)，遍历得到结果O(n);
空间复杂度：O(N),去掉输出最终结果vector的数组，没有再申请其他空间了

实现如下

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode* cur = NULL,*pre = head;
        while(pre)
        {
            ListNode* p = pre->next;   // pre之后值 
            pre->next = cur;          // 局部反转一次 
            cur = pre;               //cur 向后移动一位
            pre = p;                 //pre 向后移动一位
        }
        vector<int> ans;
        while(cur)                 //反转之后cur,指向反转后链表的头
        {
            ans.push_back(cur->val);
            cur = cur->next;
        }
        return ans;
    }
};