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

LeetCode - 23 合并 K 个升序链表

article 2025/2/25 11:07:42

题目来源

23. 合并 K 个升序链表 - 力扣（LeetCode）

题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 10^4

题目解析

本题是 LeetCode - 21 合并两个有序链表-CSDN博客 进阶题。

本题最简单的解题思路是：

若 lists 非空，则以 lists[0] 作为基链表 base，然后从索引 1 开始遍历 lists 的每一个元素 lists[i]，依次和 base 合并，这里 lists[i] 和 base 的合并可以套用 leetcode 21逻辑。

但是这种顺序遍历合并的时间复杂度偏高。

为了降低时间复杂度，我们可以使用分治的思路，下面画个图来对比下顺序和分治的区别：

顺序合并图示如下：

分治合并图示如下：

由于我们目前无法直接合并 K=5 个链表，即无法直接合并 [0, 4] 范围的链表，此时可以进行范围分治，将大问题分解为相同的、但是规模更小的多个子问题。

比如 [0, 4] 范围的合并结果：等价于下面两个子范围合并结果的二次合并结果

这里对大范围进行二分，即先找 [L,R] 中间点 mid，然后分解为 [L,mid] 和 [mid+1,R] 

  • [0,2] 范围
  • [3,4] 范围

那么 [0, 4] 范围的链表合并问题，就分解为了求解 [0,2] 范围链表合并、以及 [3,4] 范围链表合并。

接下来可以对子问题继续分治，比如 [0,2] 范围可以分解为：

  • [0,1] 范围
  • [2,2] 范围，此时，该范围只有一个链表，因此该范围的合并结果就是 lists[2] 链表

接下来可以对子问题继续分治，比如 [0,1] 范围可以分解为：

  • [0,0] 范围，此时，该范围只有一个链表，因此该范围的合并结果就是 lists[0] 链表
  • [1,1] 范围，此时，该范围只有一个链表，因此该范围的合并结果就是 lists[1] 链表

当子问题无法继续分治时，即分解到了最小规模子问题时（比如范围内只有一个链表），此时可以进行回溯

  • 由于 [0,0]、[1,1] 范围无法继续分治，因此它们是最小规模子问题，可以直接求解范围内链表合并结果分别为 lists[0]、lists[1]，我们假设 lists[0] 和 lists[1] 的合并结果为 a 链表，那么 [0,1] 范围的合并结果就是 a。
  • 由于已知 [0,1] 的合并结果 a，而 [2,2] 范围已经时最小规模子问题（其合并结果为 lists[2]），那么 [0,2] 范围的合并结果即为 a 和 lists[2] 的合并结果，假设为 b

同理，我们可以按照上面逻辑，求解出 [3,4] 范围的合并结果，假设为 c

那么，最终 [0,4] 范围的合并结果，即为 b 和 c 的合并结果。

C源码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* dummy_head =
        (struct ListNode*)malloc(sizeof(struct ListNode));

    dummy_head->val = 0;
    dummy_head->next = NULL;

    struct ListNode* tail = dummy_head;

    while (list1 != NULL && list2 != NULL) {
        if (list1->val < list2->val) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }

        tail = tail->next;
    }

    tail->next = list1 != NULL ? list1 : list2;

    return dummy_head->next;
}

// 将 lists 的 [l, r] 范围的链表 合并为 一个链表
struct ListNode* merge(struct ListNode** lists, int l, int r) {
    if (l == r) { // 如果只有一个链表，则直接返回对应链表
        return lists[l];
    }

    int mid = (l + r) / 2;

    // 分治
    struct ListNode* list1 = merge(lists, l, mid); // 将 lists 的 [l, mid] 范围链表 合并为 一个链表
    struct ListNode* list2 = merge(lists, mid + 1, r); // 将 lists 的 [mid+1, r] 范围链表 合并为 一个链表

    // 合并两个有序链表
    return mergeTwoLists(list1, list2);
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    if (listsSize == 0) {
        return NULL;
    }

    return merge(lists, 0, listsSize - 1);
}

C++源码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) {
            return nullptr;
        }

        return merge(lists, 0, lists.size() - 1);
    }

    // 将 lists 的 [l, r] 范围的链表 合并为 一个链表
    ListNode* merge(vector<ListNode*>& lists, int l, int r) {
        if (l == r) { // 如果只有一个链表，则直接返回对应链表
            return lists[l];
        }

        int mid = (l + r) / 2;
        
        // 分治
        ListNode* list1 = merge(lists, l, mid); // 将 lists 的 [l, mid] 范围链表 合并为 一个链表
        ListNode* list2 = merge(lists, mid + 1, r); // 将 lists 的 [mid+1, r] 范围链表 合并为 一个链表

        // 合并两个有序链表
        return mergeTwoLists(list1, list2);
    }

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy_head = new ListNode(0, nullptr);

        ListNode* tail = dummy_head;

        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val < list2->val) {
                tail->next = list1;
                list1 = list1->next;
            } else {
                tail->next = list2;
                list2 = list2->next;
            }

            tail = tail->next;
        }

        tail->next = list1 != nullptr ? list1 : list2;

        return dummy_head->next;
    }
};

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 mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }

        return merge(lists, 0, lists.length - 1);
    }

    // 将 lists 的 [l, r] 范围的链表 合并为 一个链表
    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) { // 如果只有一个链表，则直接返回对应链表
            return lists[l];
        }

        int mid = (l + r) / 2;

        // 分治
        ListNode list1 = merge(lists, l, mid); // 将 lists 的 [l, mid] 范围链表 合并为 一个链表
        ListNode list2 = merge(lists, mid + 1, r); // 将 lists 的 [mid+1, r] 范围链表 合并为 一个链表

        // 合并两个有序链表
        return mergeTwoLists(list1, list2);
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy_head = new ListNode(0, null);

        ListNode tail = dummy_head;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }

            tail = tail.next;
        }

        tail.next = list1 != null ? list1 : list2;

        return dummy_head.next;
    }
}

Python源码实现

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[Optional[ListNode]]
        :rtype: Optional[ListNode]
        """
        if len(lists) == 0:
            return None

        # 将 lists 的 [l, r] 范围的链表 合并为 一个链表
        def merge(l, r):
            if l == r:  # 如果只有一个链表，则直接返回对应链表
                return lists[l]

            mid = (l + r) // 2

            # 分治
            list1 = merge(l, mid)  # 将 lists 的 [l, mid] 范围链表 合并为 一个链表
            list2 = merge(mid + 1, r)  # 将 lists 的 [mid+1, r] 范围链表 合并为 一个链表

            # 合并两个有序链表
            return self.mergeTwoLists(list1, list2)

        return merge(0, len(lists) - 1)

    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        dummy_head = ListNode(0, None)

        tail = dummy_head

        while list1 != None and list2 != None:
            if list1.val < list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next

            tail = tail.next

        tail.next = list1 if list1 else list2

        return dummy_head.next

JavaScript源码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
    if (lists.length == 0) {
        return null;
    }

    return merge(lists, 0, lists.length - 1);
};

// 将 lists 的 [l, r] 范围的链表 合并为 一个链表
var merge = function (lists, l, r) {
    if (l == r) { // 如果只有一个链表，则直接返回对应链表
        return lists[l];
    }

    const mid = (l + r) >> 1;

    // 分治
    const list1 = merge(lists, l, mid); // 将 lists 的 [l, mid] 范围链表 合并为 一个链表
    const list2 = merge(lists, mid + 1, r); // 将 lists 的 [mid+1, r] 范围链表 合并为 一个链表

    // 合并两个有序链表
    return mergeTwoLists(list1, list2);
}

var mergeTwoLists = function (list1, list2) {
    const dummy_head = new ListNode(0, null);

    let tail = dummy_head;

    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            tail.next = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            list2 = list2.next;
        }

        tail = tail.next;
    }

    tail.next = list1 != null ? list1 : list2;

    return dummy_head.next;
};

http://www.kler.cn/a/560242.html

相关文章：

  • 【拥抱AI】GPT Researcher 源码试跑成功的心得与总结
  • STM32-智能小车项目
  • mysql对中文列值进行排序
  • HOW - 个人创业（融资篇）
  • 【JavaScript】JavaScript 常见概念 - 变量与数据类型 - 运算符 - 条件语句 - 循环 - 函数 - 数组操作 - 对象
  • Rust学习～tokio简介
  • Java集合并发安全面试题
  • 2022 年学习 Spring Boot 开发的最佳书籍
  • 【大模型】蓝耘智算云平台快速部署DeepSeek R1/R3大模型详解
  • uniapp通过概率实现一个随机抽奖
  • 如何用JAVA实现布隆过滤器？
  • WinForm中的Invoke函数
  • Dify工具的安装和使用
  • 【AIGC系列】1：自编码器（AutoEncoder, AE）
  • 使用自制工具类实现安全的密码加密与校验
  • Linux操作系统：基于Linux的入侵检测系统（IDS）研究与实践
  • Mysql 主从集群同步延迟问题怎么解决
  • 23种设计模式之《外观模式（Facade）》在c#中的应用及理解
  • 基于SpringBoot和Leaflet的邻省GDP可视化实战
  • WordPress TForce_Edition sql注入漏洞复现（CVE-2024-13478）（附脚本）