【每天学习一点算法 2025/12/11】合并两个有序链表

每天学习一点算法 2025/12/11

题目：合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

1. 递归方法看过我反转链表的应该都知道递归链表的要点。

   因为是升序的链表，所以我们每次只选当前最小的节点，剩下的部分交给递归处理

   • 终止条件：其中一个链表遍历完成

     如果list1为空（遍历完了），说明剩下的部分直接用list2就行

     如果list2为空（遍历完了），说明剩下的部分直接用list1就行

   • 递：每次选择较小的节点，向下递归调用，这样每层递归节点的值都是大于等于上一层的

   • 归：递归触底，开始逐个拼接节点

   functionmergeTwoLists(list1:ListNode|null,list2:ListNode|null):ListNode|null{// 终止条件：其中一个链表遍历完成if(!list1)returnlist2if(!list2)returnlist1// 每次选择较小的节点，将更大的节点和自己的下一节点交给递归处理if(list1.val<list2.val){list1.next=mergeTwoLists(list1.next,list2)// 返回当前递归层选择的节点returnlist1}else{list2.next=mergeTwoLists(list1,list2.next)// 返回当前递归层选择的节点returnlist2}};

2. 还有一种方法就是遍历链表，迭代出合并的结果。

   functionmergeTwoLists1(list1:ListNode|null,list2:ListNode|null):ListNode|null{// 创建一个节点用于迭代开头constprehead=newListNode(-1);letprev=prehead// 遍历链表直到其中一个链表结束while(list1!=null&&list2!=null){// 比较节点值迭代结果if(list1.val<=list2.val){prev.next=list1 list1=list1.next}else{prev.next=list2 list2=list2.next}prev=prev.next}// 合并剩余的部分prev.next=list1===null?list2:list1// 返回链表头returnprehead.next}

题目来源：力扣（LeetCode）