题解 | #从头到尾打印链表#

描述
输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
如输入{1,2,3}的链表
返回一个数组为[3,2,1]
0 <= 链表长度 <= 10000
此题有三种解法：
解法一.辅助数组
第一步：创建一个整形数组
第二步：从头到尾遍历链表，并将链表节点的值赋值给数组
第三步：将数组翻转。
c++代码如下：
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int>ans;
if(head==nullptr)
return ans;
ListNode* cur=head;
while(cur){
ans.push_back(cur->val);
cur=cur->next;
}
reverse(ans.begin(), ans.end());
return ans;
}
};</int></int>

解法二：栈
第一个遍历的节点最后一个输出，最后一个遍历的节点第一个输出。即典型的“先进后出”，可以用栈实现这种操作，每经过一个节点，把该节点放入栈中。当遍历完整个链表后再从栈顶开始逐个输出栈顶的值，此时输出栈顶的顺序已经反转过来了。
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
stack<int> B;
vector<int>ans;
if(head==nullptr)
return ans;
ListNode* cur=head;
while(cur){
B.push(cur->val);
cur=cur->next;
}
while(!B.empty()){
ans.push_back(B.top());
B.pop();
}
return ans;
}
};
解法三：递归
递归的本质也是栈的思想
要实现反过来输出链表，我们访问到每一个节点的时候，先递归输出它后面的节点，在输出该节点的自身，但是当链表非常长的时候，会导致调用的层级很深，可能导致栈溢出。</int></int></int>