剑指 offer：3、从尾到头打印链表

3. 从尾到头打印链表

题目描述

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

解题思路：

• 思路1: 利用栈先进后出的性质，将链表中的数据push到栈中，然后pop到vector中
• 思路2: 利用头插法，遍历链表，将链表元素插入到vector头部(缺点：需要多次分配空间)

解答：

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

// 解法1:
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ans;
        stack<int> nodes;
        ListNode* pNode = head;
        while(pNode != NULL)
        {
            nodes.push(pNode -> val);
            pNode = pNode -> next;
        }
        while(!nodes.empty())
        {
            ans.push_back(nodes.top());
            nodes.pop();
        }
        return ans;
    }
};
//解法2:
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ans;
        ListNode* pNode = head;
        while(pNode != NULL)
        {
            ans.insert(ans.begin(), pNode -> val);
            pNode = pNode -> next;
        }
        return ans;
    }
};

大家有兴趣可以访问我的个人博客，不定时更新一些内容哦！