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

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

目前创新互联已为近1000家的企业提供了网站建设、域名、网络空间、网站托管、服务器托管、企业网站设计、高青网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

注：设链表长度为n。语言：C++

链表结点数据结构规定如下：

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

解法1：正向遍历，借助反向迭代器实现序列逆置（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)