【剑指Offer】从尾到头打印链表

题目描述

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

算法分析

1. 使用递归的方法：

   我们可以使用递归函数，head和head->next存在的时候进入下一层，当进入最后一层的时候开始从尾部返回。

2. 使用栈的方法：

   首先遍历一遍链表，将顺序的值压栈，然后利用栈的性质（后进先出）进行打印。

代码实现

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

// 递归
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
		vector<int> result;
        helper(head, result);
        return result;
    }
    
private:
    void helper(ListNode* head, vector<int> &result){
        if(head){
            if(head -> next){
                helper(head -> next, result);
            }
            result.push_back(head -> val);
        }
    }
};


// 栈
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        stack<int> st;
        
        while (head) {
            st.push(head->val);
            head = head->next;
        }
        
        while (!st.empty()) {
            res.push_back(st.top());
            st.pop();
        }
        
        return res;
    }
};