写在前面
前两天刷题打卡，感觉东哥的代码模板没有题解中的简洁，或者那些极限优化的代码中有很多优化技巧，但今天去感受递归的含义的时候，觉得毕竟我现在是在学习算法，理解算法含义才是学习的意义。至于优化，那是之后的事，所以刷题的时候不必过于追求简洁，就像追求简洁而降低可读性一样属于走火入魔
反转链表除了双指针还有递归，东哥这章的递归反转链表讲解算得上精品之作！
具体讲解原文从：反转链表→反转前N个节点→反转局部链表，已经讲解很清楚了，这里就不画蛇添足，直接简述一下92. 反转链表 II
反转局部链表：Leetcode 92
所谓“迭代是人，递归是神！”，两者都旨在于化问题的解为子问题的解。迭代是由简单解推广到复杂解，递归严格要求父子问题解决方法相同，且需要在得到最小子问题解后倒推原问题解。
分析一下反转问题的递推结构和最小子问题
递推结构
当我们反转链表N时，其子问题为反转后继N-1链表。
递归假设N-1子问题已经解决时，我们只需考虑如何由规模N-1的子问题得到规模N父问题的解
子问题解决时得到：
- 子问题反转后的头节点 [6] ：last
- 子问题尾节点 [2] next指针: null
我们由子问题得到父问题的过程为： - 将子问题尾节点[2]→next指向父问题头节点
- 父问题头节点→next=null
至此，父问题由子问题的解得以解决，返回上一级。
基本问题
除了递推结构外，另一个关键问题就是最小子问题或终止递归条件：
- 如果是反转全部链表，自然就是检测知道子问题头节点初始next为null
if (head == NULL || head->next == NULL) {
return head;
}
- 如果是反转前N，那就添加一个计数器:n
ListNode* reverseN(ListNode* head, int n) {
if (n == 1) {
successor = head->next;
return head;
}
ListNode* last = reverseN(head->next, n - 1);
head->next->next = head;
head->next = successor;
return last;
}
- 如果反转局部，就添加两个计数器:m,n
ListNode* reverseBetween(ListNode* head, int m, int n) {
// base case
if (m == 1) {
return reverseN(head, n);
}
// 前进到反转的起点触发 base case
head->next = reverseBetween(head->next, m - 1, n - 1);
return head;
}
92. 反转链表 II
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* successor; // 后驱节点
// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode* reverseN(ListNode* head, int n) {
if (n == 1) {
// 记录第 n + 1 个节点
successor = head->next;
return head;
}
// 以 head.next 为起点，需要反转前 n - 1 个节点
ListNode* last = reverseN(head->next, n - 1);
head->next->next = head;
// 让反转之后的 head 节点和后面的节点连起来
head->next = successor;
return last;
}
ListNode* reverseBetween(ListNode* head, int left, int right) {
// base case
if (left == 1) {
return reverseN(head, right);
}
// 前进到反转的起点触发 base case
head->next = reverseBetween(head->next, left - 1, right - 1);
return head;
}
};