剑指offer系列——3.从尾到头打印链表

Q：输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
C：时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
T：
1.我直接用的reverse函数。这道题需要注意的，就是链表为空的情况。不过……应该《数据结构》里经常提到了。

# include <algorithm>
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ArrayList;
        if(head == nullptr){
            return ArrayList;
        }
        ListNode* cur = head;
        while(cur){
            ArrayList.push_back(cur->val);
            cur = cur->next;
        }
        reverse(ArrayList.begin(), ArrayList.end());
        return ArrayList;
    }

2.《数据结构》中常用的原地逆转方法。但 @假正经张先生 ，不建议直接将单链表逆置，这不符合常理，我只是要这个单链表中的逆序的值，而你却把我的单链表给我逆置了。如果我这个单链表还有其他用途，而我并不知道我的单链表被逆置了，就可能造成其他功能的错误。

    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> vec;
        ListNode *buf=head;
        ListNode *pre=buf;
        if(head == nullptr)
            return vec;
        while(head->next != nullptr){ //把buf插到head前面
            buf=head->next;
            head->next=buf->next;
            buf->next=pre;            
            pre=buf;
        }
        while(buf){
            vec.push_back(buf->val);
            buf=buf->next;
        }
        return vec;
    }

3.利用栈。

    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ret;
        
        ListNode* cur=head;
        stack<int> s;
        
        while(cur)
        {
            s.push(cur->val);//先把数据都push到栈里
            cur=cur->next;
        }
        cur=head;
        while(!s.empty())
        //这里本来想用s.top()进行判断的，结果发现，栈为空时不能调用s.top，返回是超尾-1，会报错
        {
            ret.push_back(s.top());
            s.pop();
        }
        return ret;
    }

p.s.测试：

ListNode *CreateList() {
    auto *node = new ListNode(0);
    node->next = nullptr;
    return node;
}
    int test() {
        ListNode *list = CreateList();
        ListNode *head = list;
        for (int i = 1; i < 6; i++) {
            ListNode *temp = new ListNode(i);
            list->next = temp;
            list = temp;
        }
        vector<int> array = printListFromTailToHead(head);
    }