博客

【链表OJ题】：

本题来自力扣算法题，链接：

合并两个有序链表

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

这道题目应该怎么做呢，我们用下面这个例子给大家讲解

首先我们先看一下思路，要把两个升序链表合并为一个新的 升序 链表，那么我们可以想象将两个东西弄到一起并且按顺序的弄，是不是很像串东西，也就是像用一根针穿针引线的把东西串起来。

两个链表中的节点就是我们需要串的东西，然后链表就已经相当于线了，我们现在就差一个针头，那么我们就可以创建一个针头，把他们都连起来：

那么在链表中，怎么样把他们连起来呢，那就是我们的next域了，用next域的指向去连接他们，连接之后，两个链表之前的导向就会消失，得到一个新的链表：

那么怎么将他们按顺序的串起来呢，我们要的是新的

升序链表

，要升的，所以我们要从小到大排序，那这时候我们只需要对比两个链表还没有被串起来的节点就好了。

比如说。如果链表1的节点比链表2的节点val值小，那么链表1的节点就被串起来了，然后链表1就跳到下一个节点，以下一个节点和链表2的刚刚的节点比较：

所以我们就这样一步一步的走下去就可以了，那么转换成代码怎么写呢，首先是创建一个链表。然后就是判断，当是L1的节点小于L2的节点的时候，就将L1的节点的地址给针头。如果不是就将L2的节点的地址给针头。

  if(l1.val<l2.val){
           tmp.next=l1;
           l1=l1.next;
           tmp=tmp.next;
                }
   else{
            tmp.next=l2;
            l2=l2.next;
            tmp=tmp.next;
                }

然后就是判断最后什么时候结束某一链表的连续，我们只需要判断链表是否来到null的地方就可以。然后最后还需要在前面考虑链表是否为空，就可以了。

最后合成的链表：

参考代码：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
           
            ListNode newHead = new ListNode(-1);//创建一个新节点
            ListNode tmp = newHead;//用这个去作为下一个串哪个的下标
            while(l1 != null && l2 != null){
            //当有一个不是空链表的时候就进入
                if(l1.val<l2.val){
                    tmp.next=l1;//L1的节点小的情况
                    l1=l1.next;
                    tmp=tmp.next;
                }
                else{
                    tmp.next=l2;//L2的节点小的情况
                    l2=l2.next;
                    tmp=tmp.next;
                }
            }
            if(l1 != null){
            //判断L1是否已经走完
                tmp.next = l1;
            }
            if(l2 != null){
             //判断L2是否已经走完
                tmp.next = l2;
            }
             return newHead.next;//最后返回针头
    }
}

这就是本题的解答了。