数据布局:小根堆+链表
算法:将链表中的数据先存入数组,然后建立小根堆,依次取出堆顶置于新链表
,并调整堆
- /**
- * 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企服之家,中国第一个企服评测及商务社交产业平台。 |