[water]反转链表

思路：

1.链表反转遍历版和递归版，递归版可以在前馈过程反转，结尾处回递结果，也可在结尾处反转然后回递，这里做了第一种

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};
//11:06--11:09
class Solution2 {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* head=NULL, *mid = pHead, *tail=NULL;
        if(mid==NULL)
            return NULL;
        tail = mid->next;
        while(mid!=NULL){
            mid->next = head;
            head = mid;
            mid = tail;
            tail = tail->next;
        }
        return head;
    }
};
//11:09--11:23
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        return recursion(NULL, pHead);
    }
    ListNode* recursion(ListNode* last, ListNode* current){
        if(current==NULL)
            return NULL;
        ListNode* next = current->next;
        current->next = last;
        ListNode *result = recursion(current, next);
        if(result==NULL){//都是在已经有current的情况下了
            return current;
        }else{
            return result;
        }
    }
};