ToB企服应用市场:ToB评测及商务社交产业平台
标题:
力扣23 合并k个升序链表
[打印本页]
作者:
南飓风
时间:
2024-6-15 00:28
标题:
力扣23 合并k个升序链表
数据布局:小根堆+链表
算法:将链表中的数据先存入数组,然后建立小根堆,依次取出堆顶置于新链表
,并调整堆
/**
* 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 {
//向下调整建堆
private void adjustHeap(int root, List<Integer> a, int size){
int l = root*2 + 1;
while(l < size){
if(l+1 < size && a.get(l) > a.get(l+1)){
l = l+1;
}
if(a.get(l) < a.get(root)){
int x = a.get(l);
a.set(l,a.get(root));
a.set(root,x);
root = l;
l = 2*root+1;
}
else
break;
}
}
private void createHeap(List<Integer> a, int size){
for(int r = (size-1)/2; r >= 0; r--){
adjustHeap(r,a,a.size());
}
}
public ListNode mergeKLists(ListNode[] lists) {
List<Integer> a = new ArrayList<>();
for(int i = 0; i < lists.length; i++){
ListNode p = lists[i];
while(p != null){
a.add(p.val);
p = p.next;
}
}
createHeap(a,a.size());
ListNode arr = new ListNode(),p = arr;
for(int i = 0; i < a.size(); i++){
System.out.println(a.get(0));
ListNode q = new ListNode(a.get(0));
p.next = q;
p = q;
a.set(0,a.get(a.size()-1-i));
adjustHeap(0,a,a.size()-1-i);
}
return arr.next;
}
}
复制代码
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)
Powered by Discuz! X3.4