题目描述

题目地址：

https://leetcode-cn.com/problems/merge-two-sorted-lists/

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

示例一：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例二：

输入：l1 = [], l2 = []
输出：[]

示例三：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是?[0, 50]
-100 <= Node.val <= 100
l1?和?l2?均按?非递减顺序?排列

链表节点如以下代码所示：


 
  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; }
  }

题解一：非递归

一开始没仔细读题，就想着再创建一个链表装这两个链表，看了题解之后发现很简单，只需要一个额外的节点就行了，如图:

测试用例一：1 2 4

? ? ? ? ? ? ? ? ? ? ? 1 3 4

讲解

已经是有序的两个链表，，在原空间的基础上升序它俩,可以使用归并排序的思路：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode pre = new ListNode(-1);
            ListNode p = pre;
           
            while (list1 != null && list2 != null){
                if (list1.val <= list2.val) {
                    p.next = list1;
                    list1 = list1.next;
                } else {
                    p.next = list2;
                    list2 = list2.next;
                }
                p = p.next;
            }
            if (list1 == null) p.next = list2;
            if (list2 == null) p.next = list1;
            return pre.next; 
    }
}

（为什么用两个指针指向额外的节点呢？p是作为针，连接list1和list2这两条链表的，它到最后肯定要指向list1或者list2其中一条链表的尾部的，那么pre就用来返回。）

如图，list1的第一个元素为1，list2中的第一个元素也为1，将额外的节点指向list1的第一个节点,然后将list1指针向后移动一位，同样，p也要跟着移动，因为它还要连接list2中的数据：

p.next = list1;
list1 = list1.next;
p = p.next; // p的next已经指向list1,所以这一步可以将p移动到之前list1所在的位置

?list1和list2的元素继续比较，发现list1是2，list2是1，那么将p指向list2,list2向后移一位，同样，p也要后移一位

p.next = list2;
list2 = list2.next;
p = p.next;

?list1中的2小于list2中的3，就把p指向list1，list1向后移一位，同样，p也要后移一位

??list2中的3小于list1中的4，就把p指向list2，list2向后移一位，同样，p也要后移一位

list1和list2中最后一位相等，将p指向list1，此时?将list1向后移动一位，list1指向空，代表已经没有下一次循环了

此时循环已经结束了，可是list2还剩一个孤儿没有被串起来，就要用if else 判断一下

如果list1指向为空，就代表list1已经串完了，将p.next指向list2即可

同理，如果list2指向为空，?就代表list2已经串完了，将p.next指向list1即可：

这时，把pre连接的链表伸直就是这样：

由于pre这个节点只是辅助作用，所以返回值是? pre.next?

这时你会不会有疑问，那list2剩下的元素怎么办呢？没有把他们穿起来啊，

因为这是链表，后面的元素本来就跟list2连着，把p指向list2相当于把后面的元素一起串起来了。

题解二：递归

递归过程只可意会不可言传...

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
       
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}

言传如图：

（这张图在电脑上可以看）