6剑指OFFER1.输入一个链表，从尾到头打印链表每个节点的值。

参考资料：

[1]剑指OFFER课本思路 P59
[2]如何创建单向链表。参考今天学的：http://www.cnblogs.com/skywang12345/p/3561803.html

关键词：

栈

自己的代码：

改进版：

struct ListNode {
    int m_nKey;
    ListNode * m_pNext;
};

vector<int> PrintFromTailToHead(ListNode *pHead)
{
    stack<int> staTmp;
    vector<int> vecResult;

    ListNode* pNode = pHead;

    if (pHead == nullptr)
        return vecResult;

    //把链表各个节点的值从头到尾放入栈中
    while (pNode != nullptr)
    {
        staTmp.push(pNode->m_nKey);
        pNode = pNode->m_pNext;
    }

    while (!staTmp.empty())
    {
        vecResult.push_back(staTmp.top());
        staTmp.pop();
    }

    return vecResult;
}

初始版：

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/


class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        
        //总体思路是：把链表中的数放入栈中，然后不断pop出来放入vector中
        
        stack<int> num;
         vector<int> num2;
        ListNode* pNode = head;
        
        if(pNode ==nullptr)
            return num2;
        //步骤1：把当前节点的值放入栈中
        while(pNode!= nullptr)
        {
            num.push(pNode->val);
            pNode = pNode->next;
        }
        //步骤2：将栈中的值弹出
        while(!num.empty())
        {
            num2.push_back(num.top());
            num.pop();    
        }
        return num2;
    }
};

标准答案：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct ListNode
{
    int val;
    struct ListNode* next;
    ListNode(int x):val(x),next(NULL)
    {}
};

class Solution
{
public:
    vector<int> printListFromTailToHead(ListNode* head)
    {
        vector<int> result;
        //栈：stack，类似于堆盘子。，最后叠上去的盘子首先被取下来。
        stack<int> arr;
        ListNode* p=head;
        while(p!=NULL)
        {
            arr.push(p->val);
            p=p->next;
        }
        int len = arr.size();
        for(int i=0;i<len;i++)
        {
            result.push_back(arr.top());
            arr.pop();
        }
        return result;
    }
};


int main()
{
    //不会,就类比，看别人怎么写的。
    //程序奔溃，说明哪里有问题。是的，你写的有问题，不要怀疑Qt有问题
    //如何创建单向链表
    //能不能从你今天做的得到启发啊，不然你学的没啥用啊
    //能不能做一个比较简单的单链表
    //学的还是由点效果哈，必须学以致用，否则学了半天，没用上，那就扯淡了。

    ListNode* head = new ListNode(-1);

    ListNode* pnode1 = new ListNode(0);
    head->next=pnode1;

    ListNode* pnode2 = new ListNode(1);
    pnode1->next = pnode2;

    ListNode* pnode3 = new ListNode(2);
    pnode2->next = pnode3;

    pnode3->next = NULL;

//........................................................
    Solution A;

    vector<int> result;
    result = A.printListFromTailToHead(head);
    cout<<"OK"<<endl;
    //......................................................
    //向量怎么输出呢？

    vector<int>::iterator iElementLocator = result.begin();
    while(iElementLocator != result.end())
    {
        cout<<*iElementLocator<<endl;
        ++iElementLocator;
    }

    return 0;

}

最后编辑于：2018.08.31 10:33:23