首页 > 代码库 > 【leetcode刷题笔记】Merge k Sorted Lists

【leetcode刷题笔记】Merge k Sorted Lists

2024-07-13 15:50:24   214人阅读

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

 

题解：最开始用了最naive的方法，每次在k个链表头中找出最小的元素，插入到新链表中。结果果断TLE了。

分析一下，如果这样做，每取出一个节点，要遍历k个链表一次，假设k个链表一共有n个节点，那么就需要O(nk)的时间复杂度。

参考网上的代码，找到了用最小堆的方法。维护一个大小为k的最小堆，存放当前k个list中还没有放入最终链表的最前面一个元素，然后每次从堆顶摘取最小的元素放入答案列表中，然后从该元素所在链表中再取一个元素补充到最小堆中。如果这个链表没有元素了，就不往堆里面加新元素了。到堆空时，循环结束。

在这种方法中，建堆，摘取堆顶元素后无论是否插入新元素复杂度都是O(logk)，所以n个元素总的时间复杂度就是O(nlogk)了。

代码如下：

 1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     //implements interface listNodeComparator to tell the heap how to compare two elements14     private Comparator<ListNode> listNodeComparator = new Comparator<ListNode>() {15         @Override16         public int compare(ListNode o1, ListNode o2) {17             // TODO Auto-generated method stub18             if(o1 == null)19                 return 1;20             else if(o2 == null)21                 return -1;22             23             return o1.val-o2.val;24         }25     };26     27     public ListNode mergeKLists(List<ListNode> lists) {28         if(lists == null || lists.size() == 0)29             return null;30         31         //Using a priority queue as heap32         Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(),listNodeComparator);33         34         //add all head nodes of k lists into the heap35         for(int i = 0;i < lists.size();i++)36             if(lists.get(i) != null)37                 heap.add(lists.get(i));38         39         ListNode answer = new ListNode(0);40         ListNode kepler = answer;41         42         while(!heap.isEmpty()){43             ListNode head = heap.poll();44             kepler.next = head;45             kepler = head;46             47             //if the list which we just extract elements from still has element,add it into the heap48             if(head.next != null)49                 heap.add(head.next);50         }51         52         return answer.next;53     }54 }

总结一下java实现heap的方法，实现一个 Comparator<ListNode> listNodeComparator 接口，在这个接口里主要实现compare函数告诉优先队列怎么比较两个元素的大小，然后定义一个优先队列，就可以当成堆用了，真心方便啊。


联系
我们