链表的反转

题目

输入一个链表，反转链表后，输出新链表的表头。

关于链表的反转应该是面试常考的问题了，总结一下链表的反转大概有三种解法

方法一

1、用三个指针分别指向当前节点，当前节点的前一个节点、以及当前节点后一个节点，然后进行每个节点分别反转
需要注意的是：因为单链表的指向是单向的，它始终指向下一节点，我们要进行反转，就要改变节点的指向所以在每次改变当前节点指向的时候

```/*
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {

        ListNode *q = pHead;//q代表当前节点
       ListNode *p=NULL;//前一个节点
        ListNode*r=NULL;//r保存当前节点的指向，这样避免反转之后链表 断裂的情况
         //head为当前节点，如果当前节点为空的话，那就什么也不做，直接返回null；
        if(pHead==NULL) return NULL;
        while(q!=NULL)//当前节点不为空，继续执行循环
        {

            r=q->next;////先用r保存当前节点的指向，这样避免反转之后链表 断裂的情况
            //保存完之后就开始进行链表的反转
            q->next=p;//开始进行链表的反转，使得当前节点的指向前一个节点
        //以上我们就完成了第一个节点的反转，此时当前节点不为空，循环继续，此时就要向后移动p、q。为下一次反转做准备
            p=q;
            q=r;
        }
        //当前节点为空就跳出这个循环，其中p就是最后一个节点了
        //直接输出p就是我们想要得到的反转后的链表
        return p;
    }
};

方法二：使用递归法

实现起来代码量少很多
举例来说明：
因为发现大部分问题都可以从递归角度想想，所以这道题目也从递归角度想了想。
现在需要把A->B->C->D进行反转，
可以先假设B->C->D已经反转好，已经成为了D->C->B,那么接下来要做的事情就是将D->C->B看成一个整体，让这个整体的next指向A，所以问题转化了反转B->C->D。那么，
可以先假设C->D已经反转好，已经成为了D->C,那么接下来要做的事情就是将D->C看成一个整体，让这个整体的next指向B，所以问题转化了反转C->D。那么，
可以先假设D(其实是D->NULL)已经反转好，已经成为了D(其实是head->D),那么接下来要做的事情就是将D(其实是head->D)看成一个整体，让这个整体的next指向C，所以问题转化了反转D。
上面这个过程就是递归的过程，这其中最麻烦的问题是，如何保留新链表的head指针呢？想到了两个办法。
以
A->B->C->NULL
C->B->A->NULL

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {

         if(pHead==NULL||pHead->next==NULL) return pHead;
        ListNode* newHead = ReverseList(pHead->next);
        pHead->next->next = pHead;
        pHead->next = NULL;
        return newHead

    }
};