LeetCode - 23 合并 K 个升序链表

news/2025/2/26 2:56:39

题目来源

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 的合并可以套用 CODE.html" title=leetcode>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.niftyadmin.cn/n/5867101.html

相关文章

JS作用域＋this指向 【JavaScript】

JS作用域＋this指向 【JavaScript】

JS作用域&#xff1a; 在JavaScript中&#xff0c;作用域指的是程序中变量、函数和对象可访问的上下文环境。JavaScript主要有三种作用域&#xff1a;全局作用域、函数作用域和块作用域&#xff08;ES6引入&#xff09;。 全局作用域&#xff1a;全局作用域中的变量在页面上的…
阅读更多...
自由学习记录（38）

自由学习记录（38）

python语法 def def print_receipt (store_name, items, total_price, cashier"Self-Checkout", payment_method"Credit Card"): Python 的 函数定义 语法 def print_receipt(...) → 定义了一个名为 print_receipt 的函数。store_name, items, total_…
阅读更多...
【ASP .NET Core】ASP .NET Core介绍

【ASP .NET Core】ASP .NET Core介绍

最近因为开发小游戏逐渐接触上了ASP .NET Core&#xff08;后面简称ASP&#xff09;&#xff0c;今天就来简单介绍一下&#xff0c;话不多说直接开始。 什么是ASP ASP是微软开发的Web框架&#xff0c;用于后端服务器开发。ASP可以用于开发 Web应用程序&#xff0c;如网页、网站…
阅读更多...
汽车软件︱AUTO TECH China 2025 广州国际汽车软件与安全技术展览会：开启汽车科技新时代

汽车软件︱AUTO TECH China 2025 广州国际汽车软件与安全技术展览会：开启汽车科技新时代

在汽车产业智能化与网联化飞速发展的当下&#xff0c;汽车软件与安全技术已然成为行业变革的核心驱动力。2025年11月20 - 22日&#xff0c;AUTO TECH China 2025 广州国际汽车软件与安全技术展览会将在广州保利世贸博览馆盛大开幕&#xff0c;这场展会将汇聚行业前沿成果&#…
阅读更多...
VSCode自定义快捷键和添加自定义快捷键按键到状态栏

VSCode自定义快捷键和添加自定义快捷键按键到状态栏

VSCode自定义快捷键和添加自定义快捷键按键到状态栏 &#x1f4c4;在VSCode中想实现快捷键方式执行与某些指令操作进行绑定&#xff0c;可以通过配置组合式的键盘按键映射来实现&#xff0c;另外一种方式就是将执行某些特定的指令嵌入在面板菜单上&#xff0c;在想要执行的时候…
阅读更多...
docker中配置redis

docker中配置redis

1、常规操作 docker pull redis&#xff08;默认你的docker中没有redis&#xff09; 2、查看redis是否拉取成功 docker images redis 3、创建目录&#xff0c;在你的宿主机&#xff0c;&#xff08;我是在虚机中建的centos7&#xff09;为了给redis配置文件使用 4、下载redis…
阅读更多...
51单片机编程学习笔记——点亮LED

51单片机编程学习笔记——点亮LED

大纲 器件51单片机开发板总结 安装驱动点亮LED烧录 随着最近机器人爆火&#xff0c;之前写的ROS2系列博客《Robot Operating System》也获得了更多的关注。我决定在机器人领域里再走一步&#xff0c;于是想到可以学习单片机。研究了下学习路径&#xff0c;最后还是选择先从51单…
阅读更多...
小智AI桌宠机器狗

小智AI桌宠机器狗

本文主要介绍如何利用开源小智AI制作桌宠机器狗 1 源码下载 首先下载小智源码，下载地址, 下载源码后，使用vsCode打开，需要在vscode上安装esp-idf，安装方式请自己解决 2 源码修改 2.1添加机器狗控制代码 在目录main/iot/things下添加dog.cc文件，内容如下； #include…
阅读更多...
最新文章

Copyright @ 2022~2023