基于php网站建设,建筑网名,网站内容页面怎么做,优化大师win10能用吗前言
本文主要介绍如何将多个小的升序链表合并一个大的升序链表。
需求描述
给出K个升序链接#xff0c;要求把这K个升序链表合并成一个#xff0c;并且这个链表也是升序的。
例如#xff1a;A [1,5,6]#xff0c; B [2,3,8], C [4,4,9] 将这3个链表合并成一个链表D…前言
本文主要介绍如何将多个小的升序链表合并一个大的升序链表。
需求描述
给出K个升序链接要求把这K个升序链表合并成一个并且这个链表也是升序的。
例如A [1,5,6] B [2,3,8], C [4,4,9] 将这3个链表合并成一个链表D合并后D [1,2,3,4,4,5,6,8,9]并且将D的第一个节点返回。
思路解析
我们可以采用优先级队列来实现先把每个链表的头结点放到一个优先级队列里优先级队列也叫小根堆。
在放小根堆的时候谁小就把谁放在最上面。需要注意的是我们放入的时候放入的是节点所以通过这个节点是可以访问整个链表的。
我们看下处理过程
首先把每个链接的头结点放入小根堆中124。首先弹出最小的值1。把1节点的下一个节点5放入小根堆中此时小根堆会自动调整顺序此时为2, 4, 5。将2节点弹出让1节点的next指针指向2节点并且将2节点的下一个节点6放入小根堆此时已弹出的节点为 1,2而小根堆为4, 5, 6。将4节点弹出让2节点的next指针指向4节点并且将4节点的下一个节点4放入小根堆中此时已弹出的节点为1,2,4而小根堆为4, 5, 6。依此类推每弹出一个节点拼接在已弹出节点的后面并将弹出节点的下一个节点放入小根堆中直到小根堆中所有的元素全部弹出。
好了现在整体思路有了但是现在是不是有个疑问我们在做算法时使用到了优先队列那么我们可以使用系统自带的优先队列吗
个人感觉如果是面试时这个系统自带的类只是题目中很小的一部分比如上面的题目主要考察的是如何实现这个过程而不是考察如何实现优先队列的如果没有特殊要求不让使用的话是可以使用的。当然如果考察是要实现一个优先队列我要是直接new一个PriorityQueue我估计面试官会一巴掌把我拍出来。
代码实现
链表节点定义如下
public class ListNode {public int val;public ListNode next;
}
复制代码
因为是小根堆需要一个排序算法所以定义一个比较器如下
public class ListNodeComparator implements ComparatorListNode {Overridepublic int compare(ListNode o1, ListNode o2) {return o1.val - o2.val; }
}
复制代码
合并链接
public ListNode mergeKLists(ListNode[] lists) {if (lists null) {return null;}PriorityQueueListNode heap new PriorityQueue(new ListNodeComparator());for (int i 0; i lists.length; i) {if (lists[i] ! null) {heap.add(lists[i]);}}if (heap.isEmpty()) {return null;}ListNode head heap.poll();ListNode pre head;if (pre.next ! null) {heap.add(pre.next);}while (!heap.isEmpty()) {ListNode cur heap.poll();pre.next cur;pre cur;if (cur.next ! null) {heap.add(cur.next);}}return head;
}
复制代码
这个方法参数lists代表要传进来多少个链表方法合并多个链表后返回链表的第一个节点。
时间复杂度
假设有M个链表M个链表的总节点个数为N。此时对于小根堆来说他的规模大小为M则对于小根堆来说他的操作时间复杂度为O(logM)一共有N个节点所以时间复杂度为O(N*logM)。
总结
本文主要介绍如何将多个小的升序链表合并一个大的升序链表介绍了实现这个功能的思路分析使用优先队列自动排序的特性实现了这个功能当然这里我们使用的是系统自带的优先队列其实也可以自己实现一个个人感觉没太必要就先偷个懒 ^_^
