题目描述
输入一个链表，从尾到头打印链表每个节点的值。
栈实现
要解决这个问题，肯定要遍历链表，从头到尾遍历链表，从尾到头输出值，典型的“后进先出”，自然可以想到用栈来解决。
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> vals;
stack<ListNode*> nodes;
ListNode* pNode=head;
while(pNode!=NULL){
nodes.push(pNode);
pNode=pNode->next;
}
while(!nodes.empty()){
pNode=nodes.top();
vals.push_back(pNode->val);
nodes.pop();
}
return vals;
}
};
递归实现
递归本质上是一个栈结构，要实现反过来输出链表，可以每访问到一个节点的时候，先递归输出它后面的节点，再输出节点本身。
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> vals;
PrintListReversing(head,vals);
return vals;
}
void PrintListReversing(ListNode *pNode, vector<int> &vals){
if(pNode!=NULL){
if(pNode->next!=NULL)
PrintListReversing(pNode->next,vals);
vals.push_back(pNode->val);
}
}
};
