一、题目描述

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

示例 1：

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

输出：[1,1,2,3,4,4]

示例 2：

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

输出：[]

示例 3：

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

输出：[0]

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/merge-two-sorted-lists

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、运行结果

三、解题思路

如果两个链表其中一个为空，则直接返回另一个链表即可。

新建一个链表结点作为新链表的头结点，然后各用两个指针遍历两个链表的每个结点，一个指针指向前一个结点，另一个指针指向后一个结点；如果list1链表当前结点的值比较小，则将list1链表当前结点连接到新链表的末尾；如果list2链表当前结点比较小，则将list2链表当前结点连接到新链表末尾，并在连接完成后后移相应的指针，直至其中一个链表遍历完成。

其中一个链表遍历完成后（也就是遍历该链表的两个指针均为空），则将另一个链表的剩余结点直接连接到新链表的末尾即可，从新建链表的头结点的下一个结点开始的链表就是所求的合并链表。

四、AC代码

/*** 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 list1, ListNode list2) {if(list1 == null) return list2;if(list2 == null) return list1;ListNode dummy = new ListNode(-1);  //新建链表的表头结点ListNode p = dummy;  //新建链表的工作指针//遍历链表的四个指针ListNode pre1 = list1, p1 = list1.next, pre2 = list2, p2 = list2.next;while(pre1!=null && pre2!=null){if(pre1.val < pre2.val){  //list1当前结点值较小p.next = pre1;  //将pre1结点连接到新链表末尾p = p.next;p.next = null;pre1 = p1;  //两个指针相应后移if(p1 == null) break;  //防止p1为空出错p1 = p1.next;}else {              //list2当前结点值较小，和上面的情况对称p.next = pre2;  p = p.next;p.next = null;pre2 = p2;if(p2 == null) break;p2 = p2.next;}}if(pre1 == null) p.next = pre2; //list1遍历完，将list2剩余部分直接连接到新链表尾else if(pre2 == null) p.next = pre1;return dummy.next;}
}