題目描述
輸入一個鏈表，按鏈表從尾到頭的順序返回一個ArrayList。

目前創(chuàng)新互聯(lián)已為近1000家的企業(yè)提供了網(wǎng)站建設、域名、網(wǎng)絡空間、網(wǎng)站托管、服務器托管、企業(yè)網(wǎng)站設計、高青網(wǎng)站維護等服務，公司將堅持客戶導向、應用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

注：設鏈表長度為n。語言：C++

鏈表結點數(shù)據(jù)結構規(guī)定如下：

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

解法1：正向遍歷，借助反向迭代器實現(xiàn)序列逆置（C++特性）。

vector printListFromTailToHead(ListNode* head) {
        ListNode *p;
        p = head;
        vector array;
        while(p != NULL)
        {
            array.push_back(p->val);
            p = p->next;
        }
        return vector(array.rbegin(), array.rend());
    }

時間復雜度：O(n)，空間復雜度：O(1)

解法2：借助棧先進后出的特性，將鏈表結點先入棧后出棧，再壓入序列中。

vector printListFromTailToHead(ListNode* head) {
        ListNode *p;
        p = head;
        stack s;
        while(p != NULL)
        {
            s.push(p->val);
            p = p->next;
        }
        p = head;
        vector array;
        while(p != NULL)
        {
            array.push_back(s.top());
            s.pop();
            p = p->next;
        }
        return array;
    }

時間復雜度：O(n)，空間復雜度：O(n)

解法3：遞歸

    vector array;
    vector printListFromTailToHead(ListNode* head) {
        ListNode *p;
        p = head;
        if(head != NULL)
        {
            if(head->next != NULL)
                printListFromTailToHead(head->next);
            array.push_back(head->val);
        }
        return array;
    }

時間復雜度：O(n)，空間復雜度：O(n)