剑指 Offer 25. 合并两个排序的链表

大家好，我是吴师兄。

今天继续来学习《剑指Offer》系列的一道经典题目，依旧给出了非常详细的题解和精美的配图与动画。

一、题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

二、题目解析

注意到这两个链表都是递增排序的，意味着在某个链表上，某个节点 A 在另外一个节点 B 的前面，那么合并后依旧是 A 在 B 的前面，但是它们之间有可能会增加另外一个链表上面的节点。

至于会增加哪些节点，那就需要执行一个比较的操作。

比较的操作可以通过如下的方式进行：

1、设置 dummy 为虚拟头节点，作为新链表头节点的前一个节点。

2、设置一个指针 pre，也指向虚拟节点。

3、从头到尾同时遍历 L1、L2 这两个链表，不断的比较 L1 和 L2 的每个节点，把较小的节点添加到新链表的尾部，添加成功后，相应的比较的链表节点向右移动一位。

为了帮助你更好的理解整个过程，我特意做了一组动画，点开可以查看：

#

三、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
        ListNode dummy = new ListNode(-1);

        // 设置一个指针，指向虚拟节点
        ListNode pre = dummy;

        // 通过一个循环，不断的比较 l1 和 l2 中当前节点值的大小，直到 l1 或者 l2 遍历完毕为止
        while (l1 != null && l2 != null) {
            // 如果 l1 当前节点的值小于等于了 l2 当前节点的值
            if (l1.val <= l2.val) {
                // 让 pre 指向节点的 next 指针指向这个更小值的节点
                // 即指向 l1
                pre.next = l1;
                // 让 l1 向后移动
                l1 = l1.next;
            }else {
                // 让 pre 指向节点的 next 指针指向这个更小值的节点
                // 即指向 l2
                pre.next = l2;
                // 让 l2 向后移动
                l2 = l2.next;
                
            }
            // 让 pre 向后移动
            pre = pre.next;
        }

        // 跳出循环后，l1 或者 l2 中可能有剩余的节点没有被观察过
        // 直接把剩下的节点加入到 pre 的 next 指针位置
        
        // 如果 l1 中还有节点
        if ( l1 != null) {
            // 把 l1 中剩下的节点全部加入到 pre 的 next 指针位置
            pre.next = l1;
        }

        // 如果 l2 中还有节点
        if ( l2 != null) {
            // 把 l2 中剩下的节点全部加入到 pre 的 next 指针位置
            pre.next = l2;
        }

        // 最后返回虚拟节点的 next 指针
        return dummy.next;
    }
}