力扣23 合并k个升序链表

数据布局:小根堆+链表
算法：将链表中的数据先存入数组，然后建立小根堆，依次取出堆顶置于新链表
，并调整堆

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     //向下调整建堆
13.     private void adjustHeap(int root, List<Integer> a, int size){
14.         int l = root*2 + 1;
15.         while(l < size){
16.             if(l+1 < size && a.get(l) > a.get(l+1)){
17.                 l = l+1;
18.             }
19.             if(a.get(l) < a.get(root)){
20.                 int x = a.get(l);
21.                 a.set(l,a.get(root));
22.                 a.set(root,x);
24.                 root = l;
25.                 l = 2*root+1;
26.             }
27.             else
28.                 break;
29.         }
30.     }
31.     private void createHeap(List<Integer> a, int size){
32.         for(int r = (size-1)/2; r >= 0; r--){
33.             adjustHeap(r,a,a.size());
34.         }
35.     }
36.     public ListNode mergeKLists(ListNode[] lists) {
37.         List<Integer> a = new ArrayList<>();
38.         for(int i = 0; i < lists.length; i++){
39.             ListNode p = lists[i];
40.             while(p != null){
41.                 a.add(p.val);
42.                 p = p.next;
43.             }
44.         }
46.         createHeap(a,a.size());
47.         ListNode arr = new ListNode(),p = arr;
48.         for(int i = 0; i < a.size(); i++){
49.             System.out.println(a.get(0));
50.             ListNode q = new ListNode(a.get(0));
51.             p.next = q;
52.             p = q;
53.             a.set(0,a.get(a.size()-1-i));
54.             adjustHeap(0,a,a.size()-1-i);
55.         }
56.         
57.         return arr.next;
58.     }
59. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。