一、反转整个链表
问题：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
//单链表的实现结构
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x;}
}
反转链表利用迭代不难实现，如果使用递归则有些许难度。
首先来看源码实现：
ListNode reverse(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode ret = reverse(head.next);
head.next.next = head;
head.next = null;
return ret;
}
是否看起来不知所云，而又被这如此简洁的代码所震撼？让我们一起探索一下其中的奥秘。
对于递归算法，最重要的是明确递归函数的定义。
我们的reverse函数的定义如下：
输入一个节点head,将以head为起点的链表反转，并返回反转之后的头节点。
明白了函数的定义后，在来看这个问题。比如我们想反转这个链表
那么输入reverse（head）后，会在ListNode ret = reverse(head.next);进行递归
不要跳进递归！（你的脑袋能压几个栈呀？）
根据reverse函数的定义，函数调用后会返回反转之后的头节点，我们用变量ret接收
现在再来看一下代码
head.next.next = head;
接下来：
head.next = null;
return ret;
再跳出这层递归就会得到：
神不神奇，这样整个链表就反转过来了！
递归代码就是这么简洁优雅，但要注意两个问题：
1、递归函数要有base case，不然就会一直递归，导致栈溢出
if (head == null || head.next == null) return head;
即链表为空或只有一个节点，直接返回
2、当链表递归反转后，新的头节点为ret,而head变成了最后一个节点，应该令链表的某尾指向null
head.next = null;
理解这两个问题之后，我们可以进一步深入研究链表反转的问题，接下来的问题其实均为在这个算法上的扩展。
二、反转链表前N个节点
接下来我们来看这个问题：
问题：反转链表前N个节点，并返回链表头节点
说明：1 <= N <= 链表长度
示例:
输入: 1->2->3->4->5->NULL, n = 4
输出: 4->3->2->1->5->NULL
解决思路和反转整个链表差不多，只需稍加修改
ListNode successor = null; // 后驱节点（第 n + 1 个节点）
ListNdoe reverseN(ListNode head, int n) {
if (n == 1) {
successor = head.next;
return head;
}
// 以 head.next 为起点，需要反转前 n - 1 个节点
ListNode ret = reverseN(head.next, n - 1);
head.next.next = head;
head.next = successor; // 将反转后的 head 与后面节点连接
return ret;
}
具体区别：
1、base case 变为n == 1, 同时需要记录后驱节点。
2、之前把head.next 设置为null,因为整个链表反转后，head变为最后一个节点。
现在head节点在递归反转后不一定为最后一个节点，故应记录后驱successor(第 n + 1 个节点), 反转之后将head连接上。
OK，如果这个函数你也能看懂，就离实现反转一部分链表不远了。
三、反转链表的一部分
现在我们开始解决这个问题，给一个索引区间[m, n]（索引从1开始），仅仅反转区间中的链表元素。
说明：1 <= m <= n <= 链表长度
示例：
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
猛一看很难想到思路。
试想一下，如果m == 1,就相当于反转链表的前 n 元素嘛，也就是我们刚才实现的功能：
ListNode reverseBetween(ListNode head, int m, int n) {
//base case
if (m == 1) {
return reverseN(head, n); // 相当于反转前 n 个元素
}
// ...
}
那如果m != 1 该怎么办？
如果把head的索引视为1，那么我们是想从第m个元素开始反转；
如果把head.next的索引视为1，那么我们是想从第m - 1 个元素开始反转；
如果把head.next.next的索引视为1，那么我们是想从第m - 2 个元素开始反转；
......
区别于迭代思想，这就是递归的思想，所以我们可以完成代码：
ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
return reverseN(head, n);
}
// 递归前进到触发 base case （m == 1）
head.next = reverseBetween(head.next, m - 1, n - 1);
return head;
}
至此，我们终于干掉了大BOSS！