23. 合并K个排序链表
2018-07-16 02:39:27来源:博客园 阅读 ()
知乎ID: 码蹄疾
码蹄疾,毕业于哈尔滨工业大学。
小米广告第三代广告引擎的设计者、开发者;
负责小米应用商店、日历、开屏广告业务线研发;
主导小米广告引擎多个模块重构;
关注推荐、搜索、广告领域相关知识;
题目
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
分析
前面已经做过两个有序链表的合并,只要采用二分,分而治之,两两合并即可。时间复杂度方面,合并两个链表的长度的时间复杂度是o(min(m, n)),其中m,n分别是链表的长度。二合并的长度是o(logk)的时间复杂度。所以整体的时间复杂度为o(klogn)
Code
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } if (l2 == null) { return l1; } ListNode merged = null; ListNode head = null; while (l1 != null && l2 != null) { if (head == null) { if (l1.val < l2.val) { merged = l1; l1 = l1.next; } else { merged = l2; l2 = l2.next; } head = merged; continue; } if (l1.val < l2.val) { merged.next = l1; l1 = l1.next; } else { merged.next = l2; l2 = l2.next; } merged = merged.next; } while (l1 != null) { merged.next = l1; l1 = l1.next; merged = merged.next; } while (l2 != null) { merged.next = l2; l2 = l2.next; merged = merged.next; } return head; } public ListNode mergeHelper(ListNode[] lists, int low, int high) { if (low < high) { int mid = (low + high) / 2; ListNode leftList = mergeHelper(lists, low, mid); ListNode rightList = mergeHelper(lists, mid + 1, high); return mergeTwoLists(leftList, rightList); } return lists[low]; } public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } return mergeHelper(lists, 0, lists.length - 1); } }
拓展
合并两个有序链表,之前采用的是非递归的解法。感觉代码有点长,可以采用递归的解法,缩短代码量。合并的时候选最小的元素,链表头指针后移动,递归合并即可。
public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null && l2 == null) { return null; } if (l1 == null) { return l2; } if (l2 == null) { return l1; } ListNode merged; if (l1.val > l2.val) { merged = l2; l2 = l2.next; merged.next = mergeTwoLists(l1, l2); } else { merged = l1; l1 = l1.next; merged.next = mergeTwoLists(l1, l2); } return merged; } }
相关题目
21. 合并两个有序链表
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Spire.Cloud.SDK for Java 合并、拆分Excel单元格 2020-06-09
- 合并有序两个单链表,合并后链表依然有序 2020-06-02
- 基础排序算法(附加java实现) 2020-06-02
- LeetCode 21. 合并两个有序链表 2020-05-22
- LeetCode 面试题53 - I. 在排序数组中查找数字 I 2020-05-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash