面试题6：从尾到头打印链表

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

思路1(推荐，书本上)：第一个遍历的最后一个出，最后一个遍历的第一个出，典型的‘先进后出’结构，用栈栈栈栈实现。

遍历单链表，一个个取出元素压入栈底；
元素出栈，保存进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;
        //若链表为空，可直接返回空vector;若链表不为空，则进行下面操作
        if(head!=nullptr)
        {
            stack<int> Stacklist; //声明一个STL的stack容器
            ListNode *p=head; //工作指针
            while(p!=nullptr)
            {
                Stacklist.push(p->val);//遍历链表元素并压入栈底
                p=p->next;
            }
            while(!Stacklist.empty())//遍历栈并弹出元素，保存至Arrraylist
            {
                int temp=Stacklist.top();
                Arraylist.push_back(temp);
                Stacklist.pop();
            }
        }
        return Arraylist;
    }
};

代码中需要注意的几点：

一直纠结在if(head!=nullptr)该怎样返回空的Arraylist,其实只用
```
vector<int> Arraylist;
if(head!=nullptr)
 return Arraylist;
```
一开始申请没赋值就是个空的vector,所以总结在一起就是代码里面所示。
声明一个STL的栈容器：stack<int> Stacklist;</int>
栈的各种操作：
元素入栈：stack.push(element);
得到栈顶元素：element=stack.top();
元素出栈：stack.pop();无返回值

思路2：数组翻转

遍历链表并将元素存储进Arraylist,再对Arraylist翻转即可。

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> Arraylist;
        if(head!=nullptr)
        {
            ListNode *p=head;//工作指针
            while(p!=nullptr)
            {
                Arraylist.push_back(p->val);
                p=p->next;
            }

            int length=Arraylist.size();
            int swap_count=floor(length/2.0);
            for(int i=0;i<swap_count;i++)
            {
                int temp=Arraylist[i];
                Arraylist[i]=Arraylist[length-1-i];
                Arraylist[length-1-i]=temp;
            }
        }
        return Arraylist;
    }
};