面试题6：从头到尾打印链表（c++）【剑指offer】

方式一：使用栈实现倒序输出（栈存储的是节点）

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> arraylist;
        stack<ListNode*> reverse; //使用栈结构来实现倒序输出，且这里的栈存储的是一个个节点
        ListNode *newnode=head;

        while(newnode!=nullptr){ //每经过一个节点，就把该节点放到栈中
            reverse.push(newnode);
            newnode=newnode->next;
        }

        while(!reverse.empty()){ //判断栈是否为空
            newnode=reverse.top(); //取出栈顶元素
            arraylist.push_back(newnode->val); //在容器后面添加一个元素
            reverse.pop(); //弹出栈顶元素
        }

        return arraylist;
    }
};

方式二：使用栈实现倒序输出（栈存储的是值）

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> arraylist;
        stack<int> reverse;
        ListNode *newnode=head;

        while(newnode!=nullptr){
            reverse.push(newnode->val);
            newnode=newnode->next;
        }

        int j=reverse.size();
        for(int i=0;i<j;i++){
            int a=reverse.top();
            reverse.pop();
            arraylist.push_back(a);
        }

        return arraylist;
    }
};