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

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

news 2026/6/10 15:47:27

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

题目：合并两个有序链表

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

递归方法看过我反转链表的应该都知道递归链表的要点。
因为是升序的链表，所以我们每次只选当前最小的节点，剩下的部分交给递归处理
- 终止条件：其中一个链表遍历完成
  如果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}};
```

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

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}