当前位置：首页 > news >正文

Java算法每日一题

news 2026/3/26 18:43:29

题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输入：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); } }