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

LeetCode-合并两个有序链表（021）

article 2025/3/1 7:34:42

一.题目描述

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

二.示例

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

四.解法:

方法一：递归

我们先判断链表 l1 和 l2 是否为空，若其中一个为空，则返回另一个链表。否则，我们比较 l1 和 l2 的头节点：

若 l1 的头节点的值小于等于 l2 的头节点的值，则递归调用函数 mergeTwoLists(l1.next,l2)，并将 l1 的头节点与返回的链表头节点相连，返回 l1 的头节点。
否则，递归调用函数 mergeTwoLists(l1,l2.next)，并将 l2 的头节点与返回的链表头节点相连，返回 l2 的头节点。

时间复杂度 O(m+n)，空间复杂度 O(m+n)。其中 m 和 n 分别为两个链表的长度。

五.代码

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 如果 list1 为空，直接返回 list2
        if (list1 == null) {
            return list2;
        }
        // 如果 list2 为空，直接返回 list1
        if (list2 == null) {
            return list1;
        }
        
        // 比较两个链表的当前节点值
        if (list1.val <= list2.val) {
            // 如果 list1 的当前节点值小于等于 list2 的当前节点值
            // 递归合并 list1 的下一个节点和 list2
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            // 如果 list2 的当前节点值小于 list1 的当前节点值
            // 递归合并 list1 和 list2 的下一个节点
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

注释说明
    ·空链表检查：如果 list1 或 list2 为空，直接返回另一个链表。
    ·递归合并：通过递归比较两个链表的当前节点值，选择较小的节点作为合并后的当前节点。
        ·较小节点处理：将较小节点的 next 指针指向递归合并后的结果。
    ·返回结果：返回合并后的链表头节点。