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

从尾到头打印链表：最直观的想法是，创建一个新的vector<int>变量result，然后使用一个链表节点指针p指向当前访问的链表节点，p初始化为头节点head，当p不为null时，将p所指向的节点元素值加入到result头部，然后使p指向p的下一个节点，最后返回result。

vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> result;
        ListNode *p=head;
        while(p!=NULL)
        {
            result.insert(result.begin(),p->val);
            p=p->next;
        }
        return result;
    }

idea：从尾到头打印链表，其实相当于逆序输出或者是反转输出，利用该性质，我们可以很自然的想到递归解法。

void dfs(vector<int> &result,ListNode *p)
    {
        if(p==nullptr) return;
        dfs(result,p->next);
        result.push_back(p->val);
    }
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> result;
        ListNode *p=head;
        dfs(result,p);
        return result;
    }

优化：递归本身系统内部会调用栈，那么不妨直接使用栈结构实现，正如同从头到尾访问链表，但是从尾到头打印链表，即先访问的后打印，满足栈先进后出的特点。

vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> result;
        ListNode *p=head;
        stack<int> st;
        while(p)
        {
            st.push(p->val);
            p=p->next;
        }
        while(st.size())
        {
            result.push_back(st.top());
            st.pop();
        }
        return result;
    }