面试热题（合并两个有序列表）

傷城~ 2023-10-14 18:55 34阅读 0赞

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

![a2aee646ced3a93a2a5eea20689ad4b0.jpeg][]

合并链表这类型题也是比较经典的题了，因为链表是由指针相互指向而确定位置，所以我们只需要改变某些节点的指针便可以做到对链表进行排序

![8e46c68ae98348e8a04cfe989e5d5561.png][]

今天这个方法我们用递归进行实现

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
           //一个链表为空，自然而然的返回不为空的节点
           if(list1==null){
               return list2;
           }
           if(list2==null){
               return list1;
           }
           //如果链表1的节点值小于等于链表二的节点值，递归链表1下一个节点值，选定链表1为当前节点值
           if(list1.val<=list2.val){
               list1.next=mergeTwoLists(list1.next,list2);
               return list1;
           }else{
               list2.next=mergeTwoLists(list1,list2.next);
               return list2;
           }
        }

其实有很多人不太理解这个递归，其实我觉得递归它像是一个大的工厂，每个人都有自己的责任，各司其职，但是只要有一个人发生了错误，整体团体也是完成不了最后的任务

![8df67b5dbdbd48c5b708a1228b8abbbe.png][]

拿这道题来说，显然L1或者L2为空的话，返直接返回L2或者L1,这个毋庸置疑

如果L1的链表的当前元素小于等于L2的元素，那我直接将L1的这个元素挂在最前面，至于后面是什么样子，我们完全不用担心，我只关注从下级员工干完活之后给我提交它们的任务（merge(L1.next,L2)），然后我把自己的任务附上去提交给我的顶头上司就行,每层做好自己的任务（我觉得这和贪心也有一点相像，每个阶段做的最好，最后一定是最好的）

[a2aee646ced3a93a2a5eea20689ad4b0.jpeg]: https://img-blog.csdnimg.cn/img_convert/a2aee646ced3a93a2a5eea20689ad4b0.jpeg
[8e46c68ae98348e8a04cfe989e5d5561.png]: https://img-blog.csdnimg.cn/8e46c68ae98348e8a04cfe989e5d5561.png
[8df67b5dbdbd48c5b708a1228b8abbbe.png]: https://img-blog.csdnimg.cn/8df67b5dbdbd48c5b708a1228b8abbbe.png