从尾到头打印链表

#include<algorithm>//reverse在algorithm中
//方法一：遍历链表然后将链表中的元素存入vector中，再进行reverse
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
    ListNode *p = head;
    vector<int> v;
    while(p!=NULL){
        v.push_back(p->val);
        p = p->next;
    }
    reverse(v.begin(),v.end());
    return v;
    
    }
};

//方法二：头插法生成新链表，再放入vector中
class Solution{
    public:
        vector<int> printListFromTailToHead(ListNode* head){
            ListNode *head_new = NULL;
            for(ListNode *p=head;p!=NULL;p=p->next){
                ListNode *q = new ListNode(p->val);
                q->next = head_new;
                head_new = q;
            }
            vector<int>ans;
            for(ListNode *p=head_new;p!=NULL;){
                ans.push_back(p->val);
                ListNode *q = p->next;
                delete p;
                p=q;
            }
            return ans;
        }
};

//方法三：使用指针对链表就地反转
class Solution{
    public:
    vector<int> printListFromTailToHead(ListNode* head){
        ListNode *a,*b,*c;
        c = head;
        b = NULL;
        while(c){
            a = c->next;
            c->next = b;
            b = c;
            c = a;
        }
        vector<int> ans;
        while(b){
            ans.push_back(b->val);
            b = b->next;
        }
        return ans;
    }
};

//方法四：递归
class Solution{
    public:
    vector <int>res;
    vector<int>printListFromTailToHead(ListNode* head){
    if(!head) return res;
        printListFromTailToHead(head->next);
        res.push_back(head->val);
        return res;
    }
};

总结

头插法

            for(ListNode *p=head;p!=NULL;p=p->next){
                ListNode *q = new ListNode(p->val);
                q->next = head_new;
                head_new = q;
            }

原地翻转

举例 :1->2->3->4->null
step 1:
1->null || 2->3->4->null
step 2:
2->1->null || 3->4->null
step 3:
3->2->1->null || 4->null
step 4:
4->3->2->1->null || null
setp 5:
跳出循环

结构体构造链表

结构体可以有自己的构造函数

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