MergeKSortedLists [source code]
public class MergeKSortedLists {
static
/******************************************************************************/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<> (new Comparator<ListNode> () {
@Override
public int compare (ListNode a, ListNode b) {
return a.val - b.val;
}
});
// what if some are null lists?
for (int i = 0; i < lists.length; i++) if (lists[i] != null)
pq.offer (lists[i]);
ListNode res = new ListNode (0), res_cur = res;
while (!pq.isEmpty ()) {
ListNode cur_head = pq.poll ();
assert cur_head != null;
if (cur_head.next != null)
pq.offer (cur_head.next);
res_cur.next = cur_head;
res_cur = res_cur.next;
}
return res.next;
}
}
/******************************************************************************/
public static void main(String[] args) {
MergeKSortedLists.Solution tester = new MergeKSortedLists.Solution();
}
}
如果只有两个你是肯定会做的; 这题就是在k=2的基础上的延伸; 那么能不能通过降维类比来得到一些启发;
这种一点例子都没给的题目, 不代表你就不需要分析例子, 相反, 反而要格外的注意自己提出有意义的例子, 然后思考可能的突破口;
从2的情况里面提炼规律, 那么k的情况应该是可以得到一个直接的思路的, 就是维护所有的list的head; 但是你怎么找当前的min? 另外能做到什么复杂度? 我感觉是N + KlgK;
很愉快的直接就AC了, 速度是23ms (22%), 毕竟hard, 可以接受好吧;
一些小的插曲, 一开始我初始化PriorityQueue的时候, 用的是
for (ListNode node : lists)
pq.offer (node);
但是这个最后导致假如lists里面有Null, 也会被offer进去:
Exception in thread "main" java.lang.NullPointerException
at java.util.PriorityQueue.offer(PriorityQueue.java:292)
at Solution.mergeKLists(Solution.java:11)
at __DriverSolution__.__helper__(__Driver__.java:4)
at __Driver__.main(__Driver__.java:48)
注意要会看这个trace, 这个trace发生在pq.offer (node). 注意, 这里最后的exception是在PriorityQueue里面, 不是在我的函数里面, 所以这里并不是说pq是Null, 而是更可能是参数node是Null;
解决办法就是用最老土的方法来iterate算了; 我当时之所以想要用在这里用foreach, 是因为之前碰到一个问题, 是自己先new了一个array, 然后用foreach当时来初始化每一个entry, 然后没有成功, 当时形成的印象就是, foreach这种自动iterate的其实是右值, 所以会自动跳过Null; 但是当时这个结论是有问题的, 这里看来, 并不会自动跳Null, 当时没有初始化成功, 纯粹是因为没有右值而已; 这里不同, 这里的lists是题目给的, 他故意插入了一些Null, 没错, Null也可以做右值. 所以你用foreach iterate的时候, 是走过了一些Null的;
editorial
Approach #1 Brute Force [Accepted]
```Pythonclass Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
self.nodes = []
head = point = ListNode(0)
for l in lists:
while l:
self.nodes.append(l.val)
l = l.next
for x in sorted(self.nodes):
point.next = ListNode(x)
point = point.next
return head.next
### Approach #2 Compare one by one [Accepted]
Algorithm
* Compare every k nodes (head of every linked list) and get the node with the smallest value.
* Extend the final sorted linked list with the selected nodes.
### Approach #3 Optimize Approach 2 by Priority Queue [Accepted]
```python
from Queue import PriorityQueue
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
head = point = ListNode(0)
q = PriorityQueue()
for l in lists:
if l:
q.put((l.val, l))
while not q.empty():
val, node = q.get()
point.next = ListNode(val)
point = point.next
node = node.next
if node:
q.put((node.val, node))
return head.next
他这里分析的复杂度是NlgK, 想想, 他是对的, 因为最后有N个iteration; 然后每一次put/get的cost是lgK. 我之前想的太简单, PriorityQueue最长是K, 所以cost to maintain is KlgK. 这个就总结过度了, 还是要分析实际的操作的复杂度;
Approach #4 Merge lists one by one [Accepted]
Convert merge
k lists problem to merge 2 lists (
k-1) times.
这个复杂度还是挺野的, 复杂度是KN;
Approach #5 Merge with Divide And Conquer [Accepted]
跟上面的方法是类似的, 但是先把K个list进行两两分组, 然后各自完成merge, 然后继续分组; 这个想法将上面的复杂度也提升到了NlgK.
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
amount = len(lists)
interval = 1
while interval < amount:
for i in range(0, amount - interval, interval * 2):
lists[i] = self.merge2Lists(lists[i], lists[i + interval])
interval *= 2
return lists[0] if amount > 0 else lists
def merge2Lists(self, l1, l2):
head = point = ListNode(0)
while l1 and l2:
if l1.val <= l2.val:
point.next = l1
l1 = l1.next
else:
point.next = l2
l2 = l1
l1 = point.next.next
point = point.next
if not l1:
point.next=l2
else:
point.next=l1
return head.next
可以看到这个题目大部分的方法还是依赖跟merge2问题的类比; 最后采用的方法, 一个是用归纳推广的思路(editorial3), 一个就是直接reduce(editorial5).
discussion最优解, 几乎是跟我的一样的:
@reeclapple said in A java solution based on Priority Queue:
If someone understand how priority queue works, then it would be trivial to walk through the codes.
My question: is that possible to solve this question under the same time complexity without implementing the priority queue?
public class Solution {
public ListNode mergeKLists(List<ListNode> lists) {
if (lists==null||lists.size()==0) return null;
PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){
@Override
public int compare(ListNode o1,ListNode o2){
if (o1.val<o2.val)
return -1;
else if (o1.val==o2.val)
return 0;
else
return 1;
}
});
ListNode dummy = new ListNode(0);
ListNode tail=dummy;
for (ListNode node:lists)
if (node!=null)
queue.add(node);
while (!queue.isEmpty()){
tail.next=queue.poll();
tail=tail.next;
if (tail.next!=null)
queue.add(tail.next);
}
return dummy.next;
}
}
下面就是有人跟出的用divide&conquer做的思路:
@wksora said in A java solution based on Priority Queue:
I think my code's complexity is also O(nlogk) and not using heap or priority queue, n means the total elements and k means the size of list.
The mergeTwoLists functiony in my code comes from the problem [Merge Two Sorted Lists][1] whose complexity obviously is O(n), n is the sum of length of l1 and l2.
To put it simpler, assume the k is 2^x, So the progress of combination is like a full binary tree, from bottom to top. So on every level of tree, the combination complexity is n, beacause every level have all n numbers without repetition. The level of tree is x, ie logk. So the complexity is O(nlogk).
for example, 8 ListNode, and the length of every ListNode is x1, x2,
x3, x4, x5, x6, x7, x8, total is n.on level 3: x1+x2, x3+x4, x5+x6, x7+x8 sum: n
on level 2: x1+x2+x3+x4, x5+x6+x7+x8 sum: n
on level 1: x1+x2+x3+x4+x5+x6+x7+x8 sum: n
total 3n, nlog8
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode head=null;
ListNode former=null;
while (l1!=null&&l2!=null) {
if (l1.val>l2.val) {
if (former==null) former=l2; else former.next=l2;
if (head==null) head=former; else former=former.next;
l2=l2.next;
} else {
if (former==null) former=l1; else former.next=l1;
if (head==null) head=former; else former=former.next;
l1=l1.next;
}
}
if (l2!=null) l1=l2;
former.next=l1;
return head;
}
public ListNode mergeKLists(List<ListNode> lists) {
if (lists.size()==0) return null;
if (lists.size()==1) return lists.get(0);
if (lists.size()==2) return mergeTwoLists(lists.get(0), lists.get(1));
return mergeTwoLists(mergeKLists(lists.subList(0, lists.size()/2)),
mergeKLists(lists.subList(lists.size()/2, lists.size())));
}
}
[1]: https://oj.leetcode.com/problems/merge-two-sorted-lists/
代码很干净漂亮, 注意他这里的这个recursion结构的构造, 以及subList函数的使用(两个参数应该是一个[left, riht)形式的index);
另外, 这个merge2其实也是好长时间没有写了, 你现在还会写吗? 注意他这里用的是一个leaf结构的判断;
复杂度:
@reeclapple said in A java solution based on Priority Queue:
Suppose the total number of nodes is n The total time complexity if (n * log k) .For a priority queue, insertion takes logK time
底下一个人一言不合自己实现了一个heap? 不知道什么意思:
@hhzsls said in A java solution based on Priority Queue:
use heap
public class Solution {
class Heap {
public List<ListNode> heap;
private int getLimit() {
return heap.size() - 1;
}
Heap(List<ListNode> lists) {
heap = new ArrayList<ListNode>();
heap.add(new ListNode(0));
int i = 0;
while (i < lists.size()) {
if (lists.get(i) != null)
heap.add(lists.get(i));
++i;
}
}
public void heapAdjust(int n, int m) {
ListNode value = new ListNode(0);
copy(heap.get(n), value);
for (int i = 2 * n; i <= m; i *= 2) {
if (i < m && heap.get(i).val > heap.get(i + 1).val)
i++;
if (heap.get(i).val >= value.val)
break;
copy(heap.get(i), heap.get(n));
n = i;
}
copy(value, heap.get(n));
}
private void copy(ListNode s, ListNode t) {
if (s == null)
s = new ListNode(t.val);
t.next = s.next;
t.val = s.val;
}
public void creatMinHeap() {
for (int i = getLimit() / 2; i > 0; --i)
heapAdjust(i, getLimit());
}
public ListNode getHeap() {
if (heap.size() == 1)
return null;
if (heap.get(1) == null) {
return null;
}
ListNode result = new ListNode(0);
copy(heap.get(1), result);
if (heap.get(1).next != null)
copy(heap.get(1).next, heap.get(1));
else {
copy(heap.get(heap.size() - 1), heap.get(1));
heap.remove(heap.size() - 1);
}
if (heap.size() != 1)
heapAdjust(1, getLimit());
return result;
}
public int getlen() {
return heap.size() - 1;
}
}
public ListNode mergeKLists(List<ListNode> lists) {
Heap h = new Heap(lists);
h.creatMinHeap();
ListNode result = null;
if (h.getlen() != 0)
result = h.getHeap();
else
return result;
ListNode temp = result;
while (h.getlen() != 0 && temp != null) {
temp.next = h.getHeap();
temp = temp.next;
}
return result;
}
}
有空再看了;
看到一个讨论PriorityQueue和heap的区别的帖子: https://softwareengineering.stackexchange.com/questions/254947/difference-between-a-heap-and-a-priority-queue
感觉还是没有讲清楚;
这里:
My interpretation is that the former is an abstract data type that orders by a generic “priority” and the latters are actual data structure implementations that either put Min (or Max) at the root and guarantee an increasing (or decreasing) ordering in its children.
所以好像其实PriorityQueue才是一个abstract/interface的样子; heap好像是最efficient的实现方式;
另外一个用divide&conquer的做法, 不过不依赖recursion, 有意思:
@zxyperfect said in Sharing my straightforward C++ solution without data structure other than vector:
ListNode *mergeKLists(vector<ListNode *> &lists) {
if(lists.empty()){
return nullptr;
}
while(lists.size() > 1){
lists.push_back(mergeTwoLists(lists[0], lists[1]));
lists.erase(lists.begin());
lists.erase(lists.begin());
}
return lists.front();
}
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
if(l1 == nullptr){
return l2;
}
if(l2 == nullptr){
return l1;
}
if(l1->val <= l2->val){
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
else{
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
The second function is from Merge Two Sorted Lists.
The basic idea is really simple. We can merge first two lists and then push it back. Keep doing this until there is only one list left in vector. Actually, we can regard this as an iterative divide-and-conquer solution.
注意, 他这里两两分组的时候, 并不需要考虑奇偶性的问题; 上面那个recursion的做法的奇偶性问题实际上是在计算中点(size / 2 in recursive call arguments of subList)的时候自动handle了;
一个改进:
@lei.liu.509 said in Sharing my straightforward C++ solution without data structure other than vector:
check my c++ solution, without using push_back, erase, which is time consuming,
use only 34ms
class Solution {
public:
ListNode *mergeTwoLists(ListNode* l1, ListNode* l2) {
if (NULL == l1) return l2;
else if (NULL == l2) return l1;
if (l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
ListNode *mergeKLists(vector<ListNode *> &lists) {
if (lists.empty()) return NULL;
int len = lists.size();
while (len > 1) {
for (int i = 0; i < len / 2; ++i) {
lists[i] = mergeTwoLists(lists[i], lists[len - 1 - i]);
}
len = (len + 1) / 2;
}
return lists.front();
}
};
注意看他这里处理奇偶性的方法也是除法: len / 2.
@Fanchao said in Sharing my straightforward C++ solution without data structure other than vector:
The time complexity is O(knlogk). And for those who get O(nk^2) here, this is where you are wrong:
In a divide and conquer method, we first divide all lists into pairs, and merge each pair separately. Then, we divide the merged lists into pairs, and merge them separately, and this goes on until there's only one list. If you get O(n*k^2) as the time complexity, it's not the flaw of the divide-and-conquer method, it's because you are doing it in a wrong way, where you first merge any two of all the lists, and use this merged list to merge with a new list, as haoxun has suggested. This will definitely have an untolerable time complexity. @haoxun
题外话, 这个divide&conquer的方法虽然也是NlgK, 但是计算方式跟PriorityQueue的方法是有区别的; PriorityQueue的方法, 是因为有N个iteration, 每一个iteration里面一个insert, 需要lgK的时间; 而这里divide&conquer的方法, 其实是因为有lgK个iteration, 然后每一个iteration是N(aggregate起来所有的lists to be merged).
@mouqi123 said in My simple java Solution use recursion:
public static ListNode mergeKLists(ListNode[] lists){
return partion(lists,0,lists.length-1);
}
public static ListNode partion(ListNode[] lists,int s,int e){
if(s==e) return lists[s];
if(s<e){
int q=(s+e)/2;
ListNode l1=partion(lists,s,q);
ListNode l2=partion(lists,q+1,e);
return merge(l1,l2);
}else
return null;
}
//This function is from Merge Two Sorted Lists.
public static ListNode merge(ListNode l1,ListNode l2){
if(l1==null) return l2;
if(l2==null) return l1;
if(l1.val<l2.val){
l1.next=merge(l1.next,l2);
return l1;
}else{
l2.next=merge(l1,l2.next);
return l2;
}
}
类似的思路, 无非是这个人把recursion的部分拆分到了一个单独的函数里面;
another:
@ofLucas said in My simple java Solution use recursion:
I did the same implementation as you. This is 3ms beating 93%
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return mL(lists, 0, lists.length - 1);
}
private ListNode mL(ListNode[] lists, int l, int r) {
if (r < l) return null;
if (r == l) return lists[r];
int mid = (l + r) / 2;
ListNode a = mL(lists, l, mid), b = mL(lists, mid + 1, r);
ListNode dmHead = new ListNode(0), cur = dmHead;
while (a != null && b != null) {
if (a.val < b.val) {
cur.next = a;
a = a.next;
} else {
cur.next = b;
b = b.next;
}
cur = cur.next;
}
cur.next = (a != null) ? a : b;
return dmHead.next;
}
}
类似的:
@robinjia said in Simple Java Merge Sort:
For this problem, use merge sort is simple and fast, I wonder why some guys solve it use PriorityQueue.
I think the complexity is k n logk. Because the recursion depth is logK, and in each level, every element will be compared.
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0)
return null;
return mergeKLists(lists, 0, lists.length - 1);
}
private ListNode mergeKLists(ListNode[] lists, int start, int end) {
if (start == end) {
return lists[start];
} else if (start < end){
int mid = (end - start) / 2 + start;
ListNode left = mergeKLists(lists, start, mid);
ListNode right = mergeKLists(lists, mid + 1, end);
return mergeTwoLists(left, right);
} else {
return null;
}
}
mergeTwoLists is base on the Merge Two Sorted Lists problem.
底下一堆瓜批还在吵复杂度, 不看了, 这题的复杂度分析一点都不难;
submission最优解: 12(97):
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
return helper(lists, 0, lists.length - 1);
}
private ListNode helper(ListNode[] lists, int s, int e) {
if (s == e) return lists[s];
int m = s + (e - s) / 2;
ListNode l = helper(lists, s, m);
ListNode r = helper(lists, m + 1, e);
return merge(l, r);
}
// 1-2-3
// 3-4-5
private ListNode merge(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (a != null && b != null) {
if (a.val < b.val) {
cur.next = a;
a = a.next;
} else {
cur.next = b;
b = b.next;
}
cur = cur.next;
}
if (a != null) cur.next = a;
if (b != null) cur.next = b;
return dummy.next;
}
}
就是divide&conquer的方法;
Problem Description
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Difficulty:Hard
Total Accepted:198.5K
Total Submissions:709.3K
Contributor:LeetCode
Companies
googlefacebookmicrosoftamazonuberlinkedintwitterairbnbixl
Related Topics
linked listdivide and conquerheap
Similar Questions
Merge Two Sorted ListsUgly Number II