剑指offer题目训练4：从尾到头打印链表

输入一个链表的头结点，按照 从尾到头 的顺序返回节点的值。

返回的结果用数组存储。

样例

输入：[2, 3, 5]
返回：[5, 3, 2]

1. 思路，本题思路比较多，如果要使用vector或者stack的话比较方便，这里奉上雪大的vector简单用法,主要用了

   vector.rbegin vector.rend 指针顺序是从尾到头输出的.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
         vector<int> res;
        //顺序遍历一遍存入vector
        while(head){
            res.push_back(head->val);
            head=head->next;
        }
        //rbegin,rend从尾到头new一个vector
        return vector<int>(res.rbegin(),res.rend());
        
    }
};

1. 自己记得以前学c的时候学过链表反转，用的是双指针，没走一步把next反转过来直到最后一个元素，然后再遍历一遍新的链表即可。

   代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
         vector<int> res;
        if(head==NULL) return res;
        ListNode* p=head;
        ListNode* q=head->next;
        //p q双指针往后走
        while(q!=NULL){
            //r存储q下一步的位置
            ListNode* r=q->next;
            //到达最后一个元素,交换next,更改头指针
            if(q->next==NULL) {
              q->next=p;
              head->next=NULL;
              head=q;
              break;
            }
            //变换方向
            q->next=p;
            //继续往后走
            p=q;
            q=r;
         
        }
       
        //反转的链表进行遍历
        while(head!=NULL){
            res.push_back(head->val);
            head=head->next;
        }
        return res;
        
    }
};