21.合并两个有序链表

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

示例 1：

img

1
2
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
  1. 如何同时对比两个链表的值？
  2. 最后如何返回头结点？

Solution：双指针

并没有创建一个临时的节点，而是直接把链表的next指向了l1 or l2，值得学习

双指针+备份

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1); // 创建一个哨兵节点，以便于在其后添加合并后的节点
        ListNode prev = prehead; // 'prev' 用于跟踪新链表的最后一个节点

        // 当两个链表都不为空时，选择两个链表中较小的头节点，添加到新链表中
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) { // 如果 l1 的值小于等于 l2 的值
                prev.next = l1; // 将 l1 添加到新链表中
                l1 = l1.next; // 移动 l1 到下一个节点
            } else { // 如果 l2 的值小于 l1 的值
                prev.next = l2; // 将 l2 添加到新链表中
                l2 = l2.next; // 移动 l2 到下一个节点
            }
            prev = prev.next; // 更新新链表的最后一个节点
        }

        // 当循环结束，l1 和 l2 中至少有一个已经完全合并到新链表中，
        // 如果 l1 或 l2 中还有剩余节点，将其直接连接到新链表的末尾
        prev.next = (l1 == null) ? l2 : l1;

        return prehead.next; // 返回合并后的链表的头节点，即哨兵节点的下一个节点
    }
}