2. 合并两个有序链表
题目描述： 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
题目链接： 21. 合并两个有序链表 - 力扣（LeetCode）
算法原理（递归）
思路
- 递归函数的含义：接收两个链表的头结点，返回合并后的头结点；
- 函数体：选择两个头结点中较小的结点作为最终合并后的头结点，然后将剩下的链表交给递归函数去处理；
- 递归处理：当某一个链表为空的时候，返回另外一个链表。
注意： 链表的题一定要画图，搞清楚指针的操作！
解法代码（C++）
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1 == nullptr) return list2;
if(list2 == nullptr) return list1;
if(list1->val < list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
} else {
list2->next = mergeTwoLists(list2->next, list1);
return list2;
}
}
};
3. 反转链表
题目描述： 给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
题目链接： 206. 反转链表 - 力扣（LeetCode）
算法原理（递归）
思路
- 递归函数的含义：接收一个链表的头指针，返回逆序后的头结点；
- 函数体：先把当前结点之后的链表逆序，逆序完之后，把当前结点添加到逆序后的链表后即可；
- 递归处理：当前结点为空或者当前只有一个结点的时候，不用逆序，直接返回。
注意： 链表的题一定要画图，搞清楚指针的操作！
