目录
1. 分析题意
2. 分析算法原理
2.1. 递归思路：
1. 挖掘子问题：
3. 编写代码
3.1. step one
3.2. step two
3.3. step three
3.1. 递归写法
4. 补充 --- 迭代写法
5. 总结
1. 分析题意
力扣上原题链接如下：
21. 合并两个有序链表 - 力扣（LeetCode）
题意：将两个升序链表合成一个新的升序链表并返回其头指针。
注意：新链表的所有节点是原链表转移过来的，不可以自己new节点。
2. 分析算法原理
2.1. 递归思路：
一个问题如果可以用递归处理，那么首先我们需要挖掘出重复的子问题。
该问题的目的：合并两个有序链表，并返回合并后的那个链表的头指针。
1. 挖掘子问题：
因为是升序，那么我们找小，lt1 < lt2，那么我们将lt1这个节点摘下来，此时接下来的问题就是合并下面的这两个有序链表。
此时我们就发现，一个大问题，可以被分为重复的子问题。因此，此时的重复子问题就是：合并两个有序链表。既然可以挖掘出重复子问题，那么就可以利用递归处理。
3. 编写代码
3.1. step one
step one：重复子问题，该过程决定了函数头的设计。经过我们上面的分析，重复子问题就是合并两个有序链表。
// 递归函数头的设计:
Node* dfs(lt1,lt2);3.2. step two
step two：只关心某一个子问题在做什么事情，这个过程决定了函数体的设计。
对于递归代码的编写，我们需要站在宏观的角度看待递归问题：我们一定要相信上面的dfs这个函数一定可以完成我们预期看到的结果：合并两个升序链表，并返回合并后的头指针。
// 某个子问题具体做的事情
(1): 比大小
// 当l1 < l2
(2): l1->next = dfs(l1->next,l2);
(3): return l1;
// 当l1 > l2
(2): l2->next = dfs(l1,l2->next);
(3): return l2;3.3. step three
step three：当一个问题不可以在被分为相同子问题的时候，就是递归结束条件；这个过程决定了递归的出口；例如上面，当其中一个链表走到空了，那么返回另一个链表即可。
// 递归结束条件
if(!l1) return l2;
if(!l2) return l1;3.4. 递归代码
根据上面的分析，我们就可以简单的写出我们的递归代码了：
class Solution {
public:
// step one:
ListNode* mergeTwoLists(ListNode* lt1, ListNode* lt2) {
// step three:
if(!lt1) return lt2;
if(!lt2) return lt1;
// step two:
if(lt1->val < lt2->val)
{
lt1->next = mergeTwoLists(lt1->next,lt2);
return lt1;
}
else
{
lt2->next = mergeTwoLists(lt1,lt2->next);
return lt2;
}
}
};4. 补充 --- 迭代写法
迭代写法，就是依次比较，得到小的哪一个节点，摘下来，当一个走到空，就结束循环，把另一个链表剩余的节点连接起来即可。迭代写法以前就实现过，在这里不细谈。
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(!list1) return list2;
if(!list2) return list1;
ListNode* newhead = nullptr;
ListNode* newtail = nullptr;
while(list1 && list2)
{
if(list1->val < list2->val)
{
if(newhead == nullptr)
{
newhead = newtail = list1;
}
else
{
newtail->next = list1;
newtail = list1;
}
list1 = list1->next;
}
else
{
if(newhead == nullptr)
{
newhead = newtail = list2;
}
else
{
newtail->next = list2;
newtail = list2;
}
list2 = list2->next;
}
}
if(list1)
newtail->next = list1;
else
newtail->next = list2;
return newhead;
}
};5. 总结
循环(迭代) 和 递归：
递归的核心：需要挖掘重复子问题
循环：同样解决的是重复的问题
因此循环可以改递归，递归可以改循环。
但是一般情况下：递归展开图可以分为多分支和单分支
多分支 ---> 递归不好改循环
单分支 ---> 递归比较容易改循环(但有些特殊情况也非常麻烦)
递归的展开图就是对一棵树做深度优先遍历（DFS），其次，中序遍历只局限于二叉树中。
