当前位置：首页 > article >正文

leetcode hot100刷题日记——29.合并两个有序链表

article 2025/8/25 17:26:33

在这里插入图片描述
解答：

方法一：递归
递归的边界条件是啥呢？
递归别想那么多具体步骤，考虑大步骤，小的递归自己会去做的

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {//递归比较大小//先考虑递归边界是什么？//如果一条链表遍历到了空节点，说明另一条链表已经排好序了//返回另一条链表if(!list1){return list2;}if(!list2){return list1;}//如果两条链表都还是非空，说明还在递归过程中//如果list1的当前节点值<list2的当前节点值// 那么我们应该把递归返回的链表放在list1的后面if(list1->val<list2->val){list1->next=mergeTwoLists(list1->next,list2);return list1;}//否则，我们就应该把递归返回的链表放在list2的后面list2->next=mergeTwoLists(list1,list2->next);return list2;}
};

时间复杂度：O(n+m)
空间复杂度：O(n+m)

方法二：迭代
参考灵山大大的题解写的
哨兵节点其实就是虚拟头节点

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode dummy{};auto cur=&dummy;while(list1&&list2){if(list1->val<list2->val){cur->next=list1;list1=list1->next;}else{cur->next=list2;list2=list2->next;}cur=cur->next;}cur->next=list1?list1:list2;return dummy.next;}
};