递归的实践——反转链表
一、递归的思想
1、确定递归函数的功能：必须确定该函数是做什么的，这也是写程序的第一步。
2、寻找零号问题（Base case）：即找出递归结束的条件。找到最终的那个问题后，它能够直接给出结果，不必再往下走了。
3、拆解，找出函数的等价关系式：每一层的问题都应该比上一层的小，不断缩小问题的 size，才能从大到小到 base case；
二、题目
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
三、思路分析
为了方便说明一个问题，这里以链表1->2->3->4->5->6->NULL, m = 3, n = 5为例进行分析如何用递归思想求解该题目。
在这里head指向的结点1，不用关注其后的所有结点时如何将m=3与n=5之间的部分反转的，它只需要知道反转后的结果就可以。也就是说，在这里递推公式reverseBetween的含义是：将拿到的链表反转，然后返回反转后的链表的头结点。
这样就可以初步写出如下的代码：
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode* between = reverseBetween(head->next, m-1,n-1);
}接着要做的就是，将递推公式reverseBetween返回的结果，挂在head之后，即head.next=between。
这时，代码可以进一步完善，如下所示：
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode* between = reverseBetween(head->next, m-1,n-1);
head->next = between;
return head;
}
递推公式的部分已经完成了，接着要明确的就是递归终止条件。在这里原问题是反转链表：1->2->3->4->5->6->NULL, m = 3, n = 5之间的部分。
更小的子问题是反转链表：2->3->4->5->6->NULL, m = 2, n = 4之间的部分。
在进一步是反转链表：3->4->5->6->NULL, m = 1, n = 3之间的部分。但是，这时这个子问题和上一个子问题还是可以用相同思路求解的同一个子问题吗？
可以 看出，不是！！！
原因在于对于子问题：2->3->4->5->6->NULL, m = 2, n = 4来说，它只需要将其之后的所有结点反转之后的结点挂在自己之后就可以了。但是，对于问题3->4->5->6->NULL, m = 1, n = 3来说，结点3本身也是需要反转的。
对于如何用递归思想反转3->4->5->6->NULL, m = 1, n = 3一会儿再说。到这里，递归终止条件就明了了，即m=1时停止，代码如下：
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (m == 1) {
return 待补充
}
ListNode* between = reverseBetween(head->next, m-1,n-1);
head->next = between;
return head;
}
接着我们看下如何用递归思想反转3->4->5->6->NULL, m = 1, n = 3，即如何反转链表的前n个结点。
这里，递推公式reverseTopN的含义是反转链表的前n个结点并返回被反转的链表的头结点。因此，其需要的参数有两个，一是待反转的链表的头结点，二是反转前几个结点，即n
对于链表4->5->6->NULL, n = 2来说，经过递推公式reverseTopN处理之后，结果如下图所示：
至此，对于反转链表的前n个结点，可以初步写出如下的代码：
ListNode* reverseTopN(ListNode* head, int n) {
ListNode* newHead = reverseTopN(head->next, n-1);
}写过反转链表递归的，我们知道，head指向的结点3也是需要反转的，即head->next->next=head。但是，我们发现在完成这一步操作后，结点6没法在和其它结点产生联系了。
这个问题怎么解决呢？我们可以用topNSuccessor这个变量，指向第n个结点之后的结点。
这时，在反转结点3，即head->next->next=head之后，我们可以将topNSuccessor指向的结点挂在head指向的结点之后，即head->next=topNSuccessor。
head->next->next=head
最后，反转从位置 m 到 n 的链表的递归实现完整代码如下：
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (m == 1) {
return reverseTopN(head, n);
}
ListNode* between = reverseBetween(head->next, m-1,n-1);
head->next = between;
return head;
}
ListNode* topNSuccessor = nullptr;
ListNode* reverseTopN(ListNode* head, int n) {
if (n == 1) {
topNSuccessor = head->next;
return head;
}
ListNode* newHead = reverseTopN(head->next, n-1);
head->next->next = head;
head->next = topNSuccessor;
return newHead;
}
四、最后总结
递归的思想相对迭代思想，稍微有点难以理解，处理的技巧是：不要跳进递归，而是利用明确的定义来实现算法逻辑。处理看起来比较困难的问题，可以尝试化整为零，把一些简单的解法进行修改，解决困难的问题
参考：
力扣