一、题目描述

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

二、解题思路

这道题参考一个题解写的非常好的up主的解释，讲解的很到位，方法是使用递归，在这道题中如何理解递归过程呢？先来举个例子：

根据题意，我们知道我们的任务是要将两个升序链表合并为一个升序的新链表！

这就好比，军训的时候，有两个小组，每一组都是按照身高，从左往右依次站立的。

这时候，教官让我们两个小组，合并为一个小组，并且也要按照身高来站立。

这个时候，是不是感觉题目，有一点温度了，人间，又充满阳光了？

跟着你的感觉，我们来想象一下如何正确的合并成一个小组，流程如下：

首先，我们给小组命名，一组为 A，一组为 B，新组合的的 C 组。

对比 A 组和 B 组现在站在最前面的人的身高，矮的先出来，站在 C 组第一位。

然后再次对比两组开头的人的身高，矮的又站出来，站在 C 组第二位。

就这样周而复始，最终，AB 两组的人，全部站到了 C 组，我们的任务也就完成了。

而我们实现该逻辑的方法，就是：递归！

现在用图的方式来展示一下，看完大家就一目了然这个递归过程了：

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2PdXQYB2-1624503222050)(C:\Users\86182\AppData\Roaming\Typora\typora-user-images\image-20210624102809009.png)]$

先比较两个链表的头结点，值小的先找到新的队列里面去。

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dEaVshHo-1624503222053)(C:\Users\86182\Desktop\image-20210624103245837.png)]$

接下来比较A组中的新的头结点A.val(2)和B的头结点B.val(1)，值小的加入队列。

在这里插入图片描述

继续头结点的比较

看到这个图解步骤，有没有一目了然呢，带到代码里去在看看怎么实现的。

三、代码演示

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {
       public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
           //首先将链表为空的情况先解决了        if(l1==null){
               return l2;        }        if(l2==null){
               return l1;        }		//两个链表的头结点比较，值小的加入到队列        if(l1.val

分析一下21行到26行的逻辑：当l1链表中的头结点小于l2中的头结点的时候，此时l1链表就作为新的链表存储最终所有节点，l1的next指向的是递归调用判断后新的值，递归判断的是原l1链表的next值（也就是上面图解中的第二步，头结点变成了2，因为1已经被插入到新的链表了），每次递归调用返回较小值所在链表。

总结

这里是参考了大佬的一些题目解析和自己的一些见解，不足之处还望指教，可能也有错误，虚心求教。

转载地址：http://gogki.baihongyu.com/

你可能感兴趣的文章