「力扣」 21. 合并两个有序链表

「力扣」 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 均按 非递减顺序 排列

题解

迭代

可以通过迭代的方式计算，首先定义一个哑节点dummy，最后返回dummy.next即可，再定义一个指针指向哑节点，后续不断将节点追加到p上即可。

首先l1和l2两个指针都指向了两个链表的头节点，如下图：

此时比较l1和l2的值大小，因为l1 > l2则执行p.next = l2，l2指针后移l2 = l2.next，p指针后移p = p.next，效果如下图：

此时l1依然在1的位置，l2已经移动到了3的位置，此时l1.val <= l3.val，所以p指针指向l1链表中的1，l1指针向后移动一位，l2保持不变，p指针后移p = p.next，效果如下图：

此时l1指向了2节点，l2指向3节点，l1.val <= l2.val，所以p.next = l1，l1指针向后移动一位，l2指针保持不变，p指针后移p = p.next，效果如下图：

此时指针l1指向了红色链表的4节点，指针l2指向了蓝色链表的2节点，继续判断，l1.val > l2.val，所以将p指针指向l2，也就是p.next = l2，然后l2指针向后移动一位，l1指针不变，p指针向后移动一位，效果图如下：

此时l1指向红色链表的4节点，l2指向蓝色链表的4节点，l1 <= l2， 所以要将p指向l1，也就是p.next = l1，l1指针向后移动一位，此时l1 = null，l2保持不变，指针p向后移动一位，如下图所示：

因为l1 = null，所以此时不会再次向后迭代，但是l2指向的4节点还没有添加到新链表中，不能丢弃它，所以直接将当前的p指针，指向l2即可。

白色箭头就是最终的链表。

上面根据具体例子分析了如何实现合并链表的功能，接下来通过代码来实现下：

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    // 定义哑节点，哑节点的值是无意义的。
    ListNode dummy = new ListNode();
    // 定义p指针，用于拼接节点，初始的时候指向哑节点
    ListNode p = dummy;
    // 迭代，当list1或者list2有一个是空的时候，则停止迭代。
    while(list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            p.next = list1;
            list1 = list1.next;
        } else {
            p.next = list2;
            list2 = list2.next;
        }
        p = p.next;
    }
    // 迭代完成后，有可能有一个链表还有节点未被迭代到，则附加到结尾即可。
    p.next = list1 == null ? list2 : list1;
    return dummy.next;
}

提交到力扣：