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

c++三种解法

顺序输入再反转

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ans;
        while(head){
            ans.push_back(head->val);
            head=head->next;
        }
        //可以直接使用库函数reverse()
        int tmp=0;
        for(int i=0;i<ans.size()/2;i++){
            tmp=ans[i];
            ans[i]=ans[ans.size()-1-i];
            ans[ans.size()-1-i]=tmp;
        }
        return ans;
    }
};

利用递归实现栈的效果来反转

class Solution {
public:

    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ans;
        if(!head) return ans;
        ans=printListFromTailToHead(head->next);
        ans.push_back(head->val);
        return ans;
    }
};

先判断终止条件，然后处理当前节点：将本节点结果放在上一个节点结果的后面。

反转链表再输出

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode* pre=NULL;
        ListNode* cur=head;
        ListNode* tmp;
        while(cur){
            tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
        vector<int> ans;
        while(pre){
            ans.push_back(pre->val);
            pre=pre->next;
        }
        return ans;
    }
};

反转链表需要三个节点：前一个，当前的，以及用来保护现场的临时节点。