一题一算法2018-02-05（从尾到头打印链表）

题目描述：

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

题目分析：

题目的主要点就是从尾到头输出，链表的是顺序的结构，所以我们首先想到的是找一个东西存起这个链表，之后将中间的这个存放结构首尾倒置。

思路一：

我们直接使用Vector存放之后再使用vector的库函数reverse，来倒置这个vector，我们将其输出就完成整个题目。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
          val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        struct ListNode *p = head;
        vector<int> listV;
        while(NULL != p){
            listV.push_back(p->val);//将值放入结果vector中
            p = p->next;
        }
        reverse(listV.begin(),listV.end());//首尾倒置
        return listV;
    }
};

思路二：

从尾到头，让我们想到了另一个结构----栈,先进后出，那我们就需要将节点读入栈中，之后我们从栈中读出放入结果返回的vector中，实现我们的需求。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
          val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        struct ListNode *p = head;
        vector<int> listV; //存放结果的vector
        stack<ListNode *> nodes;//将每个节点存入栈中
        while(NULL != p){
            nodes.push(p);
            p = p->next;
        }
        
        while(!nodes.empty()){ // 出栈，后进先出
            p = nodes.top();   //获取栈顶
            listV.push_back(p->val);
            nodes.pop(); //出栈
        }
        return listV;
    }
};

思路三：

我之前没有想到，之后看到别的，想到了这个问题，我们通过递归的方式来从尾到头的输出。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
          val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> listV;
        if(NULL != head){
            listV.insert(listV.begin(), head->val);//插入到listV的begin之前
            if(head->next != NULL){//没有下一个node
                vector<int> temp = printListFromTailToHead(head->next);
                if(temp.size() > 0){
                    listV.insert(listV.begin(), temp.begin(), temp.end());//将递归的数据插入到结果集的最前面
                }
            }
        }
        return listV;
    }
};

                                                                                                     2018年2月5日

最后编辑于：2018.02.05 12:45:21