【剑指offer】登峰造极之从尾到头打印链表

题目链接

从尾到头打印链表.
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M 热度指数：1254529

题目描述

/**

• struct ListNode {

•    int val;
  

•    struct ListNode *next;
  

•    ListNode(int x) :
  

•          val(x), next(NULL) {
  

•    }
  

• };
  */

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

解题思路

我们遍历一次链表，将链表中的val记录下来，将值再按照链表从尾到头打印出来。那么如何将值按照链表从尾到头打印出来，此时我们应该想到栈。栈的特点是数据先进后出，此时打印的值符合从尾到头打印链表。

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
    //题目要求将数据放入vector中
        vector<int> v;
        stack<ListNode*> node;
        ListNode* code;
        while(head != NULL)
        {
            node.push(head);
            head = head->next;
        }
        
        while(!node.empty())
        {
            code = node.top();
            v.push_back(code->val);
            node.pop();
        }
        return v;
    }
};