剑指offer——链表：从尾到头打印链表

1、新写一个函数，递归调用这个函数

1、数组如果作为函数参数，需要取地址——如果不取地址，返回的数组为空

2、为什么结束条件是node为空，不是node的下一个为空

        如果node的下一个为空返回，就会略过node为尾的节点，直接递归回来了，把倒数第二个元素的值压入数组了

3、函数内的顺序为什么是先判断，再回调，再存值啊？

        先判断，先确定回调的边界，防止调用过多

        先回调，再存值，是因为先回调，保证先拿到节点，再存值，做成拿节点，存值，再拿前一个节点，再存值，保证是逆序的拿到节点

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode* node=head;
        vector<int> ans;
        func(node,ans);
        return ans;
    }
    void func(ListNode* node,vector<int> &ans)
    {
        if(node==nullptr)
            return;
        func(node->next,ans);
        ans.push_back(node->val);
    }
};

2、原地反转链表

是把pre和pre的next，也就是curr之间的指向反转嘛，然后再把curr变成next

翻转链表流程：先存要被断开的，后半段已经存储了，可以直接改变当前元素的指向了，指向前一个元素，把当前元素的值赋值给前一个（前一个元素右移一位），可以处理下一个节点了，下一个节点就是刚才存储过的那个元素，叫next，把它的值赋值给当前元素的值

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode* pre=nullptr;
        ListNode* curr=head;
        ListNode* next=nullptr;

        while (curr!=nullptr) 
        {
            //先存
            next=curr->next;
            //反转
            curr->next=pre;
            //移动
            pre=curr;
            //把存储的后半段的链表的头 赋值给当前的节点
            curr=next;
        }
        //把前一个元素赋值给当前元素
        curr=pre;
        vector<int> ans;
        while(curr!=nullptr)
        {
            ans.push_back(curr->val);
            curr=curr->next;
        }
        return ans;
    }
};