题目描述将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例输入l1 [1,2,4], l2 [1,3,4]输出[1,1,2,3,4,4]解题思路递归法比较两个链表的头节点取较小的节点作为当前节点然后递归合并剩余节点迭代法推荐用虚拟头节点简化边界处理遍历两个链表依次拼接较小的节点。Java 代码迭代法// 定义链表节点 class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } } public class MergeTwoLists { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 虚拟头节点简化链表拼接 ListNode dummy new ListNode(-1); ListNode curr dummy; // 遍历两个链表直到其中一个为空 while (list1 ! null list2 ! null) { if (list1.val list2.val) { curr.next list1; list1 list1.next; } else { curr.next list2; list2 list2.next; } curr curr.next; } // 拼接剩余的节点其中一个链表可能还有未遍历的节点 curr.next list1 null ? list2 : list1; return dummy.next; } // 测试用例打印链表 public static void printList(ListNode head) { while (head ! null) { System.out.print(head.val ); head head.next; } } public static void main(String[] args) { // 构建链表1: 1-2-4 ListNode l1 new ListNode(1, new ListNode(2, new ListNode(4))); // 构建链表2: 1-3-4 ListNode l2 new ListNode(1, new ListNode(3, new ListNode(4))); MergeTwoLists solution new MergeTwoLists(); ListNode result solution.mergeTwoLists(l1, l2); // 输出1 1 2 3 4 4 printList(result); } }答案解析虚拟头节点dummy的作用避免处理 “头节点为空” 的边界情况时间复杂度O (mn)m、n 为两个链表长度空间复杂度O (1)。