反转链表

题目：

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

示例:

输入：{1,2,3}

返回值：{3,2,1}

输入：{}

返回值：{}

说明：空链表则输出空

方法：

递归

思路：

先找到链表最后一个节点，从最后一个节点开始处理依次翻转整个链表。

首先pHead指针向后移动到底，并且设置一个新的指针newhead作为翻转后的链表的头。由于整个链表翻转之后的头就是最后一个数，所以整个过程newhead指针一直指向存放在最后一个节点的地址空间。 alt

然后pHead指针逐层返回的时候依次将pHead指向的地址赋值给pHead->next->next指针，并且一定要记得让pHead->next =NULL，也就是断开现在指针的链接，否则新的链表形成了环，下一层pHead->next->next赋值的时候会覆盖后续的值。 alt

如上所述依次递归完成反转。

代码示例：

```/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here
    if(pHead==NULL||pHead->next==NULL){
        return pHead;
    }
    //遍历到链表尾部
    struct ListNode* newhead = ReverseList(pHead->next);
    //反转
    pHead->next->next=pHead;
    pHead->next=NULL;
    return newhead;
}