剑指offer-JZ3

c++
本题考察链表的数据格式理解，以及应用方法，以及vector的一些使用函数，用来了解熟悉语言。
思路一：
读取获得，并利用反转函数

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ret;
        while(head){
            ret.push_back(head->val);
            head = head->next;
        }
        std::reverse(ret.begin(),ret.end());
        return ret;
    }
};

思路2：利用递归，从最后输出
{1,2,3,4}
函数：
------如果是 head 结束了-----返回字符串
------否则：
------------进入（head->next)；
------------赋值
------------返回

例如：
head=1 val =1 next =2; 进入函数
head=2 val = 2 next=3； 进入函数
。。。。
head=4 val = next=null 返回 定义的vector--空
------------{}----4----入str; 返回{4}
------------{4}---3----入str; 返回{4,3}
。。。。
------------{4,3,2}---1---入str; 返回{4,3,2,1}
结束

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ret;
        if(!head)
            return ret;
        ret = printListFromTailToHead(head->next);
        ret.push_back(head->val);
        return ret;
};

思路3：反转列表,记录节点反向顺序，然后压入向量，输出
需要新建一个链表
head->1->2->3->4->null => null<-1<-2<-3<-4<-*p
pre-> nullprt
cur-> head
next->cur
1: cur=1; next->2 (cur->next) ; cur->pre (1->null) pre=cur=1 cur=next=2; | pre:1->null
2: cur=2; next->3 ; cur->pre (2->1) pre=cur=2 cur=next=3; | pre:2->1->null
4: cur=4; next->null ; cur->pre (4->3) pre=cur=4 cur=next=null | pre:4->3->2->1->null;
结束

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode* pre = nullptr; //new lsit
        ListNode* cur = head;   //current node
        ListNode* nex = cur;   //next node
        while(cur){
            nex = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nex;
        }
        vector<int>  ret;
        while(pre){
            ret.push_back(pre->val);
            pre=pre->next;
        }
        return ret;
    }
};