题解 | #合并两个排序的链表#

合并两个排序的链表

目标

我们要把两个按从小到大排列的珠子串（链表）合并成一个新的按从小到大排列的珠子串。

例子

假设我们有两串珠子：

第一串珠子：1 → 3 → 5
第二串珠子：2 → 4 → 6

我们要把这两串珠子合并成一串新的珠子串，这串珠子也要按从小到大的顺序排列。

解释步骤

1. 准备一个“假头”珠子

想象我们在新珠子串的最前面放一个“假头”珠子，这个珠子实际上不参与最终的珠子串，但可以帮助我们更容易地开始合并。

ListNode dummy = new ListNode(0); // “假头”珠子
ListNode tail = dummy; // 用来记录新珠子串的最后一个珠子

2. 比较两串珠子的第一个珠子

我们从两串珠子的开头开始比较，看看哪一颗珠子更小。

第一串珠子的第一个珠子是 1。
第二串珠子的第一个珠子是 2。

显然，1 比 2 小，所以我们先把 1 放到新珠子串里。

tail.next = p1; // 把 `1` 放进去
p1 = p1.next; // 移动到第一串珠子的下一个珠子
tail = tail.next; // 移动 `tail` 指针到新珠子串的最后一个珠子

3. 继续比较并合并

我们继续比较剩下的珠子，每次都把较小的珠子放到新珠子串里。

再比较：3（第一串）和 2（第二串），2 更小，把 2 放进去。
再比较：3（第一串）和 4（第二串），3 更小，把 3 放进去。
再比较：4（第二串）和 5（第一串），4 更小，把 4 放进去。
再比较：5（第一串）和 6（第二串），5 更小，把 5 放进去。
最后，把 6 放进去。

4. 处理剩下的珠子

如果有一串珠子的珠子已经被全部放进新珠子串里，而另一串珠子还有珠子没放，我们就把剩下的珠子依次放到新珠子串里。

if (p1 != null) {
    tail.next = p1; // 如果第一串珠子还有珠子，就放进去
}
if (p2 != null) {
    tail.next = p2; // 如果第二串珠子还有珠子，就放进去
}

5. 返回新珠子串的头珠子

最后，我们返回新珠子串的第一个珠子（实际上是“假头”珠子的下一个珠子）。

return dummy.next;

示例

假设我们有两串珠子：

第一串珠子：1 → 3 → 5
第二串珠子：2 → 4 → 6

我们按照上面的步骤来合并它们：

创建“假头”珠子 dummy。
比较并放入较小的珠子：
先放入 1，再放入 2，再放入 3，再放入 4，再放入 5，最后放入 6。
处理完所有的珠子。

最终得到的新珠子串为：1 → 2 → 3 → 4 → 5 → 6。

这样，我们就得到了一个新的按从小到大排列的珠子串。

最后附上完整代码:

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 创建虚拟头节点
    ListNode dummy = new ListNode(0);
    // 创建尾指针
    ListNode tail = dummy;

    // 指向两个链表的头节点
    ListNode p1 = l1, p2 = l2;

    // 当两个链表都有节点时，比较当前节点的大小
    while (p1 != null && p2 != null) {
        if (p1.val < p2.val) {
            tail.next = p1;
            p1 = p1.next;
        } else {
            tail.next = p2;
            p2 = p2.next;
        }
        tail = tail.next; // 移动尾指针
    }

    // 如果其中一个链表还有剩余节点，直接将其链接到合并后的链表末尾
    if (p1 != null) {
        tail.next = p1;
    } else if (p2 != null) {
        tail.next = p2;
    }

    // 返回合并后的链表头节点
    return dummy.next;
}