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

输入：l1 = [1,2,4], l2 = [1,3,4]​

输出：[1,1,2,3,4,4]（合并后链表结构：1→1→2→3→4→4）​

特殊情况：​

• 其中一个链表为空（如 l1 = null），返回另一个链表；​

• 两个链表均为空（l1 = null 且 l2 = null），返回 null。​

解题思路​

合并有序链表的核心是 “比较节点值，按升序拼接”，需保证新链表始终维持升序结构。常见两种高效解法：​

1. 迭代法：通过一个 “虚拟头节点” 简化边界处理，再用两个指针分别遍历两个链表，逐次比较节点值，将较小值的节点接入新链表，直至其中一个链表遍历完毕，最后拼接剩余节点。​

1. 递归法：利用递归 “缩小问题规模”，每次比较两个链表的当前节点，选择值较小的节点作为当前合并节点，再递归合并该节点的后续链表与另一个链表，直至其中一个链表为空。

public class MergeTwoSortedLists {

// 迭代合并两个有序链表

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

// 虚拟头节点：避免处理“新链表头节点为空”的边界问题

// 实际返回的是 dummy.next（新链表的真实头节点）

ListNode dummy = new ListNode(-1);

// 游标指针：用于遍历并拼接新链表（初始指向虚拟头节点）

ListNode curr = dummy;

// 当两个链表均未遍历完毕时，循环比较节点值

while (list1 != null && list2 != null) {

if (list1.val <= list2.val) {

// 若list1当前节点值更小，将其接入新链表

curr.next = list1;

// list1指针向后移动（处理下一个节点）

list1 = list1.next;

} else {

// 若list2当前节点值更小，将其接入新链表

curr.next = list2;

// list2指针向后移动

list2 = list2.next;

}

// 游标指针向后移动（准备接入下一个节点）

curr = curr.next;

}

// 循环结束后，其中一个链表已遍历完毕，拼接剩余节点

// （剩余节点本身是有序的，直接接入即可）

curr.next = (list1 != null) ? list1 : list2;

// 返回新链表的真实头节点（跳过虚拟头节点）

return dummy.next;

}

// 测试代码（含链表构建与打印工具方法）

public static void main(String[] args) {

MergeTwoSortedLists solution = new MergeTwoSortedLists();

// 1. 构建测试链表：list1 = [1,2,4]，list2 = [1,3,4]

ListNode list1 = new ListNode(1);

list1.next = new ListNode(2);

list1.next.next = new ListNode(4);

ListNode list2 = new ListNode(1);

list2.next = new ListNode(3);

list2.next.next = new ListNode(4);

// 2. 打印原链表

System.out.print("list1：");

printLinkedList(list1);

System.out.print("list2：");

printLinkedList(list2);

// 3. 合并链表

ListNode mergedList = solution.mergeTwoLists(list1, list2);

// 4. 打印合并后链表

System.out.print("合并后：");

printLinkedList(mergedList);

}

// 工具方法：打印链表

private static void printLinkedList(ListNode node) {

while (node != null) {

System.out.print(node.val);

if (node.next != null) {

System.out.print("→");

}

node = node.next;

}

System.out.println();

}

}