[Java恶补day31] 21. 合并两个有序链表

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

示例 1：

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

示例 2：
输入：l1 = [], l2 = []
输出：[]

示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

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

知识点：
链表、指针、迭代、哨兵节点

解：
核心思想：
step1·定义哨兵节点，表示新链表，哨兵节点的下一个节点为第一个真正有元素的节点。
step2·遍历两个指针list1、list2，只要不为空，就判断哪个节点的值更小，把更小的那个节点拼接到新链表上。
step3·将剩余未拼接的节点直接拼接到新链表上。

时间复杂度：$O(m+n)$。遍历两个链表。
空间复杂度：$O(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 list1, ListNode list2) {//由于不修改原来的两个链表，因此list1、list2可分别视为指向这两个链表的指针//特殊情况判断if (list1 == null) {return list2;}if (list2 == null) {return list1;}//定义新链表，并定义指针指向链表头节点ListNode list = new ListNode(); // 哨兵节点：可避免单独处理头节点，无需特判链表为空的情况ListNode cur = list;//迭代拼接while (list1 != null && list2 != null) {//哪个节点的值小，就拼接哪个if (list1.val <= list2.val) {cur.next = list1;list1 = list1.next;} else {cur.next = list2;list2 = list2.next;}//更新遍历新链表的指针cur = cur.next;}//将剩余未拼接的节点直接拼接到cur后面cur.next = list1 == null ? list2 : list1;//头节点是空的，要从下一个节点开始return list.next;}
}

参考：
1、灵神题解