剑指Offer——从尾到头打印链表

Question

输入一个链表，从尾到头打印链表每个节点的值。

Solution

• 如果这道题目限制O(1)的存储空间的话，可以考虑反转链表，然后再打印即可

• 如果没有限制的话，遍历是从头到尾，打印是从尾到头，这个时候我们应该想到用栈，先入后出的特点。

• 时间复杂度为O(n)，空间复杂度为O(n)

Code

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        while (head) {
            stack1.push(head->val);
            head = head->next;
        }
        vector<int> res;
        while (!stack1.empty()) {
			int tmp = stack1.top();
            stack1.pop();
            res.push_back(tmp);
        }
        return res;
    }
private:
    stack<int> stack1;
};