力扣: 合并两个有序链表

需求

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

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

分析

代码:

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if( list1 == null || list2 == null ){
        return list1 == null ? list2 : list1;
    }
    ListNode preHead = new ListNode(-1);
    ListNode cur = preHead;
    while( true ){
        if( list1.val < list2.val ){
            cur.next = list1;
            list1 = list1.next;
        }else{
            cur.next = list2;
            list2 = list2.next;
        }
        cur = cur.next;
        if( list1 == null ){
            cur.next = list2;
            break;
        }
        if( list2 == null ){
            cur.next = list1;
            break;
        }
    }
    return preHead.next;
}

代码解释:

处理空链表的情况

if (list1 == null || list2 == null) {
    return list1 == null ? list2 : list1;
}

如果 list1 或 list2 其中之一为 null，则直接返回另一个链表，因为合并的结果就是另一个链表。

创建一个新链表的头节点

ListNode preHead = new ListNode(-1);
ListNode cur = preHead;

preHead 是一个虚拟头节点，用于简化后续操作，cur 指向当前的合并链表的尾部节点，初始时它指向虚拟头节点 preHead。
合并两个链表

while (true) {
    if (list1.val < list2.val) {
        cur.next = list1;
        list1 = list1.next;
    } else {
        cur.next = list2;
        list2 = list2.next;
    }
    cur = cur.next;
}

进入一个无限循环，比较 list1 和 list2 的当前节点值：
如果 list1 的值小于 list2 的值，说明 list1 的节点应当先加入合并链表。
将 cur 的 next 指向 list1，然后将 list1 移动到下一个节点。
如果 list1 的值不小于 list2，则将 cur 的 next 指向 list2 并移动 list2。
处理剩余节点

cur = cur.next;
if (list1 == null) {
    cur.next = list2;
    break;
}
if (list2 == null) {
    cur.next = list1;
    break;
}

每次循环结束后，将 cur 移动到下一个节点。
检查 list1 或 list2 是否已经遍历完：
如果 list1 为 null，将 cur.next 指向 list2（因为 list2 尚未遍历完），然后退出循环。
如果 list2 为 null，将 cur.next 指向 list1，然后退出循环。
返回合并后的链表

return preHead.next; 

返回 preHead.next，即合并后的链表的头节点（因为 preHead 是虚拟节点，实际合并后的链表从 preHead.next 开始）。

运行结果:

结尾

以上 是我对这道算法的一些遐想和延伸, 可能不是最优解, 但是算法的优化嘛 本身就是一个思索的过程, 能在这个思索和迭代的过程中有所收获和乐趣就是在成长了, 欢迎大家一起来交流更多的解答…