从尾到头打印链表

从尾到头打印链表
方法一：
先从头到尾打印链表，然后利用直接反转即可，这样最简单
利用vector容器中的反转功能
代码如下：

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
      vector<int> res;
        while(head){
            res.push_back(head->val);
            head = head->next;
        }
        return vector<int>(res.rbegin(),res.rend());

    }
};

方法二：用两个指针先将链表进行反转，在输出

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        //先将链表进行反转
        ListNode *p=NULL;//存放当前节点的前一个节点
        ListNode *q=head;//当前节点
         ListNode *r=NULL;//存放当前节点的后一个节点‘’
      //  if(head==NULL) return NULL;
        while(q!=nullptr)
        {
            r=q->next;//先保存当前节点的指向

            q->next = p;//改变当前节点的指向

            p=q;
            q=r;

        }
        //从头到尾遍历输出
        vector<int> v;//创建一个容器用来保存
        while(p)//反转后的p就是链表的第一个节点
        {
            v.push_back(p->val);
            p = p->next;
        }
        return v;

    }
};

方法三：
使用数据结构--栈（先进后出）
先将链表的各个节点的数据值入栈操作，然后出栈即可。
代码注释比较清楚，在此不赘述了

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        //用栈这种数据结构，主要是使用栈先进后出的特点，
        //这样不会改变链表的结构，这也是剑指offer中给出的方法
        stack<int>s;//创建一个栈结构
        ListNode *p = head;//p通过不断的移动，依次遍历链表
        vector<int> v;//

        while(p!=nullptr)//当节点不为空，就一直循环
        {
            s.push(p->val);//链表数据值入栈
            p = p->next;
        }
        while(!s.empty())//当栈不为空的时候，
        {
            v.push_back(s.top());//将栈顶元素依次存入Vector容器中
            s.pop();//完成链表的出栈操作
        }
        return v;//直接返回vector容器即可。打印输出链表的元素值
    }
};