Leetcode21. 合并两个有序链表

问题描述：

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

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

上代码，拿去即可运行：

package com.onlyqi.daydayup01.leetcode; import lombok.AllArgsConstructor; import lombok.Data; import java.util.Objects; public class Leetcode21 { public static void main(String[] args) { ListNode head14 = new ListNode(4); ListNode head12 = new ListNode(2, head14); ListNode head11 = new ListNode(1, head12); ListNode head25 = new ListNode(5, null); ListNode head23 = new ListNode(2, head25); ListNode head21 = new ListNode(1, head23); // 1 2 4 // 1 2 5 ListNode head = mergeTwoLists1(head11, head21); while (!Objects.isNull(head)) { System.out.println(head.val); head = head.next; } } public static ListNode mergeTwoLists1(ListNode list1, ListNode list2) { ListNode head = new ListNode(0); // 哑结点 (dummy node)，简化代码 ListNode temp = head; // temp 用于遍历新链表 // 循环条件：当两个链表都还有节点时才需要比较 while (list1 != null && list2 != null) { if (list1.val <= list2.val) { temp.next = list1; // 将 list1 当前节点接在 temp 后面 list1 = list1.next; // 只移动 list1 的指针 } else { temp.next = list2; // 将 list2 当前节点接在 temp 后面 list2 = list2.next; // 只移动 list2 的指针 } temp = temp.next; // 移动 temp 指针，准备下一次连接 } // 循环结束后，至少有一个链表已经为空。 // 将剩下的非空链表直接接到结果链表的末尾。 temp.next = (list1 != null) ? list1 : list2; return head.next; // 返回哑结点的下一个节点，即新链表的头节点 } @Data @AllArgsConstructor static class ListNode { int val; ListNode next; public ListNode(int val) { this.val = val; this.next = null; } } }

运行结果：

我要刷300道算法题，第151道。 尽快刷到200，争取每天搞一道 。