每日一题系列（day 19）
前言：
🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈
🔎🔎如果说代码有灵魂，那么它的灵魂一定是👉👉算法👈👈，因此，想要写出💚优美的程序💚，核心算法是必不可少的，少年，你渴望力量吗😆😆，想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇，我们要做的，就是斩妖除魔💥💥，打怪升级！💪💪当然切记不可😈走火入魔😈，每日打怪，拾取经验，终能成圣🙏🙏！开启我们今天的斩妖之旅吧！✈️✈️
一、合并有序链表
题目：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例1：
示例2：
提示：
- 两个链表的节点数目范围是 [0, 50]
- -100 <= Node.val <= 100
- l1 和 l2 均按 非递减顺序 排列
题解：
虽然合并有序链表是一道极为简单的题，但是这道题也是可以慢慢锻炼我们的递归思想，由浅入深。
所谓递归，当有重复子问题出现的时候可以采用的一种方法。题目给出了两个重要条件，1：不能手动创建新的节点。2：两个链表都是升序的链表。合并这两个链表，并且保证合并后的链表依旧是有序的，所以我们只能从链表的头按照顺序开始合并。
假设有两个三节点的链表，分别为l1，l2链表。首先，比较l1，l2的头结点，l1 -> val > l2 -> val，那么第一个节点我们就确定了，我们只需要将剩下的五个节点再比较出下一个节点，以此例推，直到指向空，最后返回即可。
注意：如果合并链表时其中一个链表已经指向了空，而另外一个链表
还没遍历完，这时只需要将指向空的那个链表直接指向未遍历完的链表即可（别忘了链表递增这个条件）。
代码演示：
/** * 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* mergeTwoLists(ListNode* list1, ListNode* list2) { //merge Two Lists if(list1 == nullptr) return list2;//第一个链表遍历完，则剩下的指向下一个链表 if(list2 == nullptr) return list1;//同理，第二个链表遍历完，指向剩下的第一个链表 if(list1 -> val < list2 -> val) { list1 -> next = mergeTwoLists(list1 -> next, list2);//如果l1<l2进行l1的递归 return list1; } else { list2 -> next = mergeTwoLists(list1, list2 -> next);//否则进行l2的递归 return list2; } } };
二、反转链表
题目：
给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
示例1：
示例2：
示例3：
提示：
- 链表中节点的数目范围是 [0, 5000]
- -5000 <= Node.val <= 5000
题解：
反转链表想必大家也都做过，其实这题也是可以使用递归来做的，准确说一点可以使用dfs来做。
我们把链表竖起来，其实就是一棵树，而我们想要链表翻转，我们就需要从树的叶子结点开始向上操作，而每一步操作都可以看作重复子问题，所以可以使用dfs来解决。
使用深搜来解决这道题也很简单：
1、首先既然需要先遍历到叶子结点，那么就一定是后序遍历，我们可以新建节点记录返回结果。
2、要确保当前节点的下一个节点指向空才能操作，这也就意味着，当前节点的下一个节点就是叶子结点，将当前节点的下一个节点指向自己，最后将当前节点指向空（这样递归到第一层的时候，整个反转后的链表也会指向空了）
3、剩下就是边界条件，为了防止空指针，如果head为空指针直接返回head，并且根据2，当遍历到最后一个节点时，需要返回上一层，所以当当前节点指向空的时候，返回上一层。
代码演示：
/** * 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* reverseList(ListNode* head) { return dfs(head); } ListNode *dfs(ListNode *head)//把链表看成一棵树，要想反转链表就必须要从叶子结点往上操作 { if(head == nullptr || head -> next == nullptr) return head; ListNode *NewHead = dfs(head -> next); head -> next -> next = head; head -> next = nullptr; return NewHead; } };
总结
递归逻辑三步走，首先看时候能拆分成重复子问题，再看如何执行递归，最后别忘记结束递归的边界条件！
虽然题目很简单，但是以递归的方式解决还是可以很好的锻炼我们的递归逻辑思维的，总得要一步一个脚印，慢慢的啃下这块硬骨头。
