[water_basic]链表反转

反转链表

struct ListNode {
      int val;
      struct ListNode *next;
      ListNode(int x) :
            val(x), next(NULL) {
      }
};
#include <vector>
using namespace std;

1.导入stl vector后直接反转，相当于用栈了

///////vector反转（栈）
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> v;
        while(head!=NULL){
            v.push_back(head->val);
            head = head->next;
        }
        reverse(v.begin(), v.end());
        return v;
    }
};

2.递归，用递归的栈

///////递归
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        return recursion(head);
    }
    vector<int> recursion(ListNode *head){
        vector<int> v;
        if(head != NULL){
            v = recursion(head->next);
            v.push_back(head->val);
        }
        return v;
    }
};

3.改动链表本身，链表反向

///////链表反转
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> v;
        if(head == NULL){
            return v;
        }
        ListNode *pre = NULL;
        ListNode *mid = head;
        ListNode *next = head->next;
        while (mid != NULL){
            mid->next = pre;
            pre = mid;
            mid = next;
            //cout<<pre->val<<" "<< mid->val<<endl;这一句有错误最后一个mid是null不能执行，ide会提醒有了这句下面会不执行！！！
            if(next != NULL){
                next = next->next;
            }
        }
        while(pre!=NULL){
            v.push_back(pre->val);
            //忘了加自增导致内存溢出
            pre = pre->next;
        }
        return v;
    }
};

在递归版本的时候用的CLion不知道什么缘故，居然注释会干扰代码，有的注释了出现特点的字结尾会影响执行结果（13，14行本来有注释结果14行的“上”字结尾导致下面的pre指针一直赋不了值，测试了一个上午才发现下面的注释加了也会导致return被unreachable）！！！