主要参考：
文章目录- 递归思想
- 链表
- 函数模板
- leetcode部分题目
- 206. 反转链表
- 21. 合并两个有序链表
- 234. 回文链表
- 83. 删除排序链表中的重复元素
递归的思路：
重复利用函数本身能实现的功能，按照顺序进行不断地自调用
核心: 建立递归函数
函数主要包含:
1.边界判断
2.实现需要完成的功能
3.对下一跳/项继续进行函数自身的调用
注意！！！这个评论说的很对
链表1.这个问题的子问题是什么。
2.当前层要干什么事情。
3.递归出口。想清楚这几点就好啦。
很多刚接触递归的同学习惯往深处想，就想想清楚下一层，下下层到底咋回事，千万别！这样永远也想不清楚的，你只要把当前层的事情干好，边界条件找好，深层自然而然就是对的。千万别想那么深。
参考：数据结构之链表与递归
一般来说链表递归的终止条件都为 head == NULL || head->next==NULL
递归函数function(当前节点){
终止条件判断(遍历到尽头直接 return)
剪枝条件判断(return)
这一层处理
return 下一层处理的结果
}
主函数( ){
对头节点调用函数function
返回结果
}
leetcode部分题目
leetcode中链表的声明
206. 反转链表
206. 反转链表
思路：
原地反转
迭代法：
双指针实现，可以移步我的另一篇博客：leetcode_刷题总结_先后指针/前后指针
递归法：
解法一：按双指针的思路写
因为题目最后需要返回一个链表，故可以设置为有返回的递归
递归法相和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。
关键是初始化的地方，可能有的同学会不理解， 可以看到双指针法中初始化 cur = head，pre = NULL，在递归法中可以从如下代码看出初始化的逻辑也是一样的。
class Solution {
public:
ListNode* reverse(ListNode* pre,ListNode* cur){
if(cur == NULL)//边界
return pre;
// 保存一下 cur的下一个节点，因为反转当前节点之后还需要继续递归往后走
ListNode* cur_next = cur->next;
cur->next = pre;
//对下一个节点调用reverse
return reverse(cur,cur_next);
}
ListNode* reverseList(ListNode* head) {
return reverse(NULL, head);
}
};
解法二：
直接在题目给定函数上递归：
子问题：
对现在访问的节点（这一层）进行反转构造
当前层要干什么：
- 如果head为空，说明走到尽头，直接返回head
（因为已经反转过了，虽然走到尽头，但是是反转链表的头节点） - 对当前节点（这一层）进行反转，
(head->next)->next=head
head=NULL
后面是打包好的newhead
reverseList要做的是下一层的事情，当前处理了head，head->next 就是下一层。
newhead=reverseList(head->next) 为了防止断链，前面先执行。
递归出口：
当所有节点都执行完之后，任务就完成了，就可以返回了。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 这里的head就相当于前面的cur
if (head == NULL || head->next == NULL) //边界
return head;
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
};
以链表1->2->3->4->5举例
第一轮出栈，head为5，head.next为空，返回5
第二轮出栈，head为4，head.next为5，执行head.next.next=head也就是5.next=4，
把当前节点的子节点的子节点指向当前节点
此时链表为1->2->3->4<->5，由于4与5互相指向，所以此处要断开4.next=null
此时链表为1->2->3->4<-5
返回节点5
第三轮出栈，head为3，head.next为4，执行head.next.next=head也就是4.next=3，
此时链表为1->2->3<->4<-5，由于3与4互相指向，所以此处要断开3.next=null
此时链表为1->2->3<-4<-5
返回节点5
第四轮出栈，head为2，head.next为3，执行head.next.next=head也就是3.next=2，
此时链表为1->2<->3<-4<-5，由于2与3互相指向，所以此处要断开2.next=null
此时链表为1->2<-3<-4<-5
返回节点5
第五轮出栈，head为1，head.next为2，执行head.next.next=head也就是2.next=1，
此时链表为1<->2<-3<-4<-5，由于1与2互相指向，所以此处要断开1.next=null
此时链表为1<-2<-3<-4<-5
返回节点5
出栈完成，最终头节点5->4->3->2->1
21. 合并两个有序链表
21. 合并两个有序链表
迭代法：
写得很烂请见谅
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* preHead = new ListNode(-1);//哑节点
ListNode* root = preHead;
//循环赋值
while(list1 && list2){
//分情况讨论
//list1 list2一样大 同时往后走
if(list1->val == list2->val){
root->next=list1;
list1=list1->next;
root=root->next;
root->next=list2;
list2=list2->next;
root=root->next;
continue;
}
//list1比较小
if(list1->val < list2->val){
root->next=list1;
list1=list1->next;
root=root->next;
continue;
}
//list2比较小
if(list1->val > list2->val){
root->next=list2;
list2=list2->next;
root=root->next;
continue;
}
}
//未讨论list1 or list2为空的情况
root->next = list1 == nullptr ? list2 : list1;
return preHead->next;
}
};
递归法：
参考：一看就会，一写就废？详解递归
子问题：
对现在访问的节点（这一层）进行合并构造
当前层要干什么：
- 如果list1或list2为空，直接返回list1或者list2（后面是剩下的）
- 如果list1 <= list2 ,将list1放前面，后面是打包好的mergeTwoLists，
mergeTwoLists要做的是下一层的事情，当前处理了list1，list1->next 就是下一层。
mergeTwoLists(l1->next, l2) - 如果list1 > list2 ,将list2放前面，后面是打包好的mergeTwoLists
mergeTwoLists要做的是下一层的事情，当前处理了list2，list2->next 就是下一层。
mergeTwoLists(l1, l2->next)
递归出口：
当所有节点都执行完之后，任务就完成了，就可以返回了。
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == NULL){
return l2;
}
if(l2 == NULL){
return l1;
}
if(l1->val <= l2->val){
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
if(l1->val > l2->val){
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};
234. 回文链表
双指针法:
可以移步我的另一篇博客：leetcode_刷题总结_快慢指针
递归法：
子问题：
对现在访问的节点（这一层）与头节点比较
递归从后返回节点与开头节点比较，俩个一起往中间夹击
当前层要干什么：
1、如果currentNode为空，说明走到尽头，直接返回true（前面都没错）
2、对当前节点currentNode（这一层）进行判断，
currentNode->val != frontPointer->val 返回false
currentNode->val == frontPointer->val 进入下一层判断
recursivelyCheck要做的是下一层的事情： （1）frontPointer = frontPointer->next （2）打包好的recursivelyCheck(currentNode->next)
递归出口：
当所有节点都执行完之后，任务就完成了，如果前面都没有返回false，那么最终就可以直接返回true。
class Solution {
ListNode* frontPointer;
public:
bool recursivelyCheck(ListNode* currentNode) {
if(currentNode!=NULL) {
if(!recursivelyCheck(currentNode->next)){//剪枝
return false;
}
if(currentNode->val != frontPointer->val){
return false;
}
frontPointer = frontPointer->next;
}
//递归边界
return true;
}
bool isPalindrome(ListNode* head) {
frontPointer = head;
return recursivelyCheck(head);
}
};
83. 删除排序链表中的重复元素
子问题：
对现在访问的节点（这一层）进行去重 ，返回一个去重后的链表
当前层要干什么：
1、如果head为空，说明走到尽头，直接返回
2、对当前节点head（这一层）进行去重判断，
（1）不重复=》head 返回 head
（2）重复===》head 返回 newhead
后面接上是打包好的newhead
deleteDuplicates是下一层要做的事情，即deleteDuplicates(head->next)
newhead=deleteDuplicates(head->next) 为了防止断链，前面先执行。
递归出口：
当所有节点都执行完之后，任务就完成了。
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head == NULL || head->next == NULL) //边界
return head;
ListNode* newHead = deleteDuplicates(head->next);
head->next = newHead;
if(head->val==head->next->val){//去重判断
return newHead;
}
else{
return head;
}
}
};
