当前位置: 首页 > java >正文

C语言编程--20.合并K个升序列表

C语言编程–20.合并K个升序列表

题目:

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

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

示例 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

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* merge(struct ListNode* list_a, struct ListNode* list_b) {// 边界情况:若任一链表为空,直接返回非空链表if (list_a == NULL) return list_b;if (list_b == NULL) return list_a;struct ListNode* head;        // 合并后链表的头节点struct ListNode* tail;        // 合并后链表的尾节点// 确定头节点:选择list_a和list_b中值较小的节点作为头节点if (list_a->val > list_b->val) {head = list_b;list_b = list_b->next; // 移动list_b指针,跳过已选节点} else {head = list_a;list_a = list_a->next; // 移动list_a指针,跳过已选节点}tail = head; // 尾节点初始化为头节点// 遍历剩余节点,合并两个链表while (list_a && list_b) {if (list_a->val > list_b->val) {tail->next = list_b; // 将list_b当前节点接到tail之后list_b = list_b->next; // 移动list_b指针} else {tail->next = list_a; // 将list_a当前节点接到tail之后list_a = list_a->next; // 移动list_a指针}tail = tail->next; // 更新尾节点到新接入的节点}// 处理剩余节点:将未遍历完的链表直接接到tail之后if (list_a)tail->next = list_a;elsetail->next = list_b;return head; // 返回合并后的链表头节点
}/*** @brief 合并K个有序链表(分治递归法)* @param lists 链表数组,每个元素为有序链表的头节点(可能为空)* @param listsSize 链表数组的长度* @return 合并后的有序链表头节点* @note 算法思路:* 1. 递归终止条件:若链表数组只剩1个链表,直接返回该链表* 2. 分治策略:将链表数组分成两半,递归合并每一半,最后合并两个结果* 3. 临时数组temp存储合并后的子问题结果,处理奇偶长度数组的边界情况*/
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {// 边界情况:空数组直接返回NULLif (listsSize == 0) return NULL;// 递归终止条件:只剩一个链表,直接返回if (listsSize == 1) return lists[0];// 计算中间数组的大小(向上取整),例如:// listsSize=3 → num=2;listsSize=4 → num=2int num = (listsSize + 1) / 2;// 分配临时数组,存储两两合并后的子链表struct ListNode** temp = (struct ListNode**)malloc(sizeof(struct ListNode*) * num);int i = 0; // 原数组遍历指针int j = 0; // 临时数组存储指针// 两两合并链表,处理偶数长度部分while (i < listsSize - 1) {// 合并lists[i]和lists[i+1],存入temp[j]temp[j] = merge(lists[i], lists[i + 1]);i += 2; // 每次跳两个元素j++;    // 临时数组指针后移}// 处理奇数长度的剩余链表(若存在)if (listsSize % 2) { // 等价于 i == listsSize - 1// 将最后一个未配对的链表存入temptemp[j] = lists[listsSize - 1];j++;}// 递归合并临时数组中的子链表struct ListNode* result = mergeKLists(temp, j);// 释放临时数组内存,避免内存泄漏free(temp);return result;
}

代码优点分析:

  1. 分治递归思路清晰
    通过递归将合并 K 个链表的问题拆解为合并两个有序链表的子问题,符合分治算法的设计思想,代码结构层次分明。
  2. 边界情况处理全面
    空链表数组(listsSize == 0)直接返回NULL。
    单链表情况(listsSize == 1)直接返回原链表,避免无效递归。
    奇数长度数组通过listsSize % 2判断剩余链表,确保所有链表都被处理。
  3. 内存管理意识强
    在递归调用后释放临时数组temp的内存,避免内存泄漏,符合 C 语言动态内存管理规范。
  4. 合并逻辑高效
    merge函数使用双指针遍历两个链表,时间复杂度为 O (m+n)(m 和 n 为链表长度),空间复杂度为 O (1)(原地合并)。

代码缺点分析:

  1. 递归深度可能过大
    当listsSize较大时(如 1000),递归深度可达 O (logK),虽然理论上不会溢出,但相比迭代法(如优先队列)可能占用更多栈空间。
  2. 临时数组的冗余操作
    每次递归都创建临时数组temp,虽然空间复杂度为 O (K/2 + K/4 + …) = O (K),但频繁的内存分配 / 释放可能影响性能。
    例如,当listsSize=3时,临时数组大小为 2,但实际只使用了 1 个有效元素(另一个元素未初始化)。
  3. 奇数长度处理的潜在问题
    代码中if (listsSize % 2)的判断等价于i == listsSize - 1,但更推荐直接通过i的值判断是否剩余元素,因为listsSize % 2在i未遍历完时可能不准确(虽然当前逻辑正确)。
  4. 无法处理大量空链表
    虽然代码处理了单个空链表的情况(在merge中返回非空链表),但当数组中存在大量空链表时,递归仍会遍历空指针,可优化为先过滤空链表。
http://www.xdnf.cn/news/9713.html

相关文章:

  • MFC坦克大战游戏制作
  • 禾纳ATE3156AP/ATE3156AS,P沟道增强型MOSFET,替代AO4805方案
  • 数据可视化的定义和类型
  • 基于多尺度卷积和扩张卷积-LSTM的多变量时间序列预测
  • 1、Pytorch介绍与安装
  • C++ RB_Tree
  • 数据仓库分层 4 层模型是什么?
  • 请问Java方法可以同时即是static又是synchronized的吗?
  • 国内高频混压PCB厂家有哪些?
  • react-color-palette源码解析
  • Unity 快捷键
  • Python 字符串入门指南
  • 循环神经网络(RNN)模型
  • vue3 + WebSocket + Node 搭建前后端分离项目 开箱即用
  • 执行npm命令报在此系统禁止运行脚本
  • 多模态大语言模型arxiv论文略读(九十九)
  • 【深度学习】11. Transformer解析: Self-Attention、ELMo、Bert、GPT
  • 【深度学习:进阶篇】--2.3.深度学习正则化
  • 通过远程桌面连接Windows实例提示“出现身份验证错误,无法连接到本地安全机构”错误怎么办?
  • 【Python零基础入门系列】第6篇:Python 的数据结构世界(列表、字典、集合、元组)
  • 深入解析ThreadPoolExecutor设计精髓
  • 数字孪生数据监控如何提升汽车零部件工厂产品质量
  • EasyRTC音视频实时通话助力微信小程序:打造低延迟、高可靠的VoIP端到端呼叫解决方案
  • 园区智能化集成平台汇报方案
  • uniapp 实现腾讯云 IM 消息已读回执
  • Ubuntu Zabbix 钉钉报警
  • 职坐标AI算法实战:TensorFlow/PyTorch深度模型
  • 【案例分享】蓝牙红外线影音遥控键盘:瑞昱RTL8752CJF
  • Python量化交易12——Tushare全面获取各种经济金融数据
  • LVS + Keepalived高可用群集