图解LeetCode——21. 合并两个有序链表（难度：简单）_链式有序表合并算法流程图

一、题目

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

链表节点定义如下所示：

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

二、示例

示例 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 均按 非递减顺序 排列

三、解题思路

因为题目中已经描述了，list1和list2是两个升序链表。所以，如果要拼装全新的升序列表，只需要对比两个链表中的值即可。此时需要两个指针list1和list2分别指向两个链表的对比节点。当对比出较小值时，则创建新节点new ListNode(list1.val 或 list2.val)，并拼装成为新的链表。对于新的链表，创建时result指向头节点，默认值为-1，temp指针指向当前赋值节点，当需要拼接新的链表时，可以通过temp.next = new ListNode(list2.val)和temp = temp.next来构造新的链表。具体逻辑如下图所示：

当list1和list2长度不同的时候，为了简化操作，可以将“多余”的部分直接拼装到新链表即可。如下图所示：

四、代码实现

public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode result = new ListNode(-1);
        ListNode temp = result;
        while (list1 != null && list2 != null) {
            if (list1.val >= list2.val) {
                temp.next = new ListNode(list2.val);
                list2 = list2.next;
            } else {
                temp.next = new ListNode(list1.val);
                list1 = list1.next;
            }
            temp = temp.next;
        }
        temp.next = (list1 == null) ? list2 : list1;
        return result.next;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的点赞&分享。

更多技术干货，欢迎大家关注公众号“爪哇缪斯”(^o^)/~ 「干货分享，每周更新」

好文推荐

LeetCode精讲——565. 数组嵌套（难度：中等）

LeetCode精讲——2. 两数相加（难度：中等）

LeetCode精讲——735. 行星碰撞（难度：中等）

LeetCode精讲——1252. 奇数值单元格的数目（难度：简单）

题目来源：力扣（LeetCode）