合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6
来源:力扣(leetcode)
链接:
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
很明显的topk问题;
步骤:
算法复杂度: n为节点总数
步骤:
算法复杂度: n为节点总数
package leetcode; import java.util.comparator; import java.util.priorityqueue; /** * @author zhoujie * @date 2020年1月10日 下午8:26:09 * @description: 23. 合并k个排序链表 * */ public class leetcode_0023 { } // definition for singly-linked list. class listnode_0023 { int val; listnode_0023 next; listnode_0023(int x) { val = x; } } class solution_0023 { /** * @author zhoujie * @date 2020年1月10日 下午8:48:38 * @description: todo(方法简述) * @return listnode_0023 * @updateuser-updatedate:[zhoujie]-[2020年1月10日 下午8:48:38] * @updateremark:1-使用优先队列 * */ public listnode_0023 mergeklists_1(listnode_0023[] lists) { if (lists == null) { return null; } // 优先队列,非基础类型需要重写比较器 priorityqueue<listnode_0023> queue = new priorityqueue<listnode_0023>(new comparator<listnode_0023>() { public int compare(listnode_0023 o1, listnode_0023 o2) { return o1.val - o2.val; } }); for (listnode_0023 node : lists) { if (node != null) { queue.add(node); } } listnode_0023 head, now; head = now = null; while (!queue.isempty()) { listnode_0023 node = queue.poll(); if (head == null) { head = now = node; } else { now.next = node; now = node; } if (node.next != null) { queue.add(node.next); } } return head; } /** * @author zhoujie * @date 2020年1月10日 下午9:03:07 * @description: todo(方法简述) * @return listnode_0023 * @updateuser-updatedate:[zhoujie]-[2020年1月10日 下午9:03:07] * @updateremark:2-分治思想,不断折半合并,直至为一个; * */ public listnode_0023 mergeklists_2(listnode_0023[] lists) { int len; if (lists == null || (len = lists.length) == 0) { return null; } while (len > 1) { for (int i = 0; i < len / 2; i++) { // 对半合并,后一半合并到前一半 lists[i] = mergehelper(lists[i], lists[len - 1 - i]); } len = (len + 1) / 2; } return lists[0]; } /** * @author: zhoujie * @date: 2020年2月4日 下午2:45:50 * @param: @param l1 * @param: @param l2 * @param: @return * @return: listnode_0023 * @description: 合并两个有序链表辅助方法 * */ private listnode_0023 mergehelper(listnode_0023 l1, listnode_0023 l2) { if (l1 == null) { return l2; } else if (l2 == null) { return l1; } else if (l1.val < l2.val) { l1.next = mergehelper(l1.next, l2); return l1; } else { l2.next = mergehelper(l1, l2.next); return l2; } } }
如对本文有疑问, 点击进行留言回复!!
SpringBoot引用阿里easyexcel,Excel导出返回浏览器下载
HashMap、Hashtable、ConcurrentHashMap三者间的异同
解决RecycleView 中Item包含Edittext时,滑动view复用导致数据错乱的问题
多线程、同步工作原理、死锁案例、Lock接口、线程的生命周期的讲解及实现
网友评论