从尾到头打印链表

题目描述

输入一个链表，从尾到头打印链表每个节点的值。

栈实现

要解决这个问题，肯定要遍历链表，从头到尾遍历链表，从尾到头输出值，典型的“后进先出”，自然可以想到用栈来解决。

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);
        }
            
    }
        
};