21.合并两个有序链表
原题链接:https://leetcode-cn.com/problems/merge-two-sorted-lists/
题目:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = []
输出:[]
示例 3:
输入:l1 = [], l2 = [0]
输出:[0]
提示:
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
C++递归解法:
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1 == nullptr){ //如果list1为空,则返回list2
return list2;
}else if(list2 == nullptr){ //如果list2为空,则返回list1
return list1;
}else if(list1->val < list2->val){ //如果list2中的数大于list1中的数,则调用递归比较list1下一位的数和list2中的数比较,且如果list1为新链表第一位,则以list1为表首
list1 -> next = mergeTwoLists(list1->next , list2);
return list1; //最后返回list1为首的新链表
}else{ //如果list1中的数大于list2中的数,则调用递归比较list2下一位的数和list1中的数比较,且如果list2为新链表第一位,则以list2为表首
list2 -> next = mergeTwoLists(list1 , list2->next);
return list2; //最后返回list2为首的新链表
}
}
};
思想:
主要解法是利用递归,但是可能有很多人不理解这道题的递归是怎么递归的。
其实很简单,就如我上图所画的。利用两个链表的每个节点进行比较,最开始进行比较的那个节点最小,就以那个节点为首,这也就是为什么我们要返回为首的那个链表,后面的值会在操作中进行覆盖。
每次比较都会记录最小的节点,然后指向下一个节点同上一个节点进行比较,最后直接进行返回,就如上图形成了一个新链表。