题目
定义一个方法，实现输入一个链表的头结点，然后可以反转这个链表的方向，并输出反转之后的链表的头结点。
解题之法
typedef struct Node{
int data;
Node *next;
} Node, *List;
//递归方式
Node* reverseList(List head)
{
//如果链表为空或者链表中只有一个元素
if(head == NULL || head->next == NULL)
{
return head;
}
else
{
//先反转后面的链表，走到链表的末端结点
Node* newhead = reverseList(head->next);
//再将当前节点设置为后面节点的后续节点
head->next->next = head;
head->next = NULL;
return newhead;
}
}
分析
递归的方法其实是非常巧的，它利用递归走到链表的末端，然后再更新每一个node的next 值 ，实现链表的反转。
而newhead 的值没有发生改变，为该链表的最后一个结点，所以反转后，我们可以得到新链表的head。
假设一个链表如下：
boke_0.png
程序刚开始执行，if 语句失效，进入 else 语句，然后执行Node* newhead = reverseList(head->next);第二个结点的指针参数传入递归函数，一直到最后一个结点的指针参数传入递归函数，if 语句有效head->next == NULL，返回当前的head 给 newhead 指针指向，如图：
boke_1.png
其实在递归函数栈内，按照后进先出的顺序，执行一级级的递归函数，返回末位结点给 newhead 之后，执行递归栈里的第二个递归函数，发生如图：
boke_2.png
返回 newhead，也就是新的反转之后的链表（临时的），然后进入到递归工作栈里的第一个递归函数，如图：
boke_3.png
返回 newhead，也就是反转之后的链表，此时递归工作栈的函数全部执行，返回的结点就是反转之后的链表的头结点（之前的尾结点）
本篇博客内容转载自[《全面分析再动手的习惯：链表的反转问题（递归和非递归方式）》][0]
[0]: http://www.cnblogs.com/kubixuesheng/p/4394509.html
