解
第一步，万年不变的查错。如果给的list是null或空，直接return
public ListNode mergeKLists(List<ListNode> lists) {
if (lists == null || lists.size() == 0) {
return null;
}
...
}
最简单的方法当然还是PriorityQueue了，先建一个能比较node的PriorityQueue。
Queue<ListNode> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
然后把每个list的头节点放进pq里面，顺便忽略null的list。其实这里也可以把list的每一个点放进去，不过这样会加大PriorityQueue的深度，也忽略了每个list都是排好序的特质。如果没有排过序，那么必须每个都放进去，既然现在排过了，就不需要在一开始就全放进去了。
for (ListNode list : lists) {
if (list != null) {
pq.add(list);
}
}
然后就是从pq里面poll出最小的了。先建一个dummy用来存放开头的位置，然后一个current是跟着加入的node不断变的。每poll出一个，都要查看一下有没有next，如果有的话，再把next放回去。最后返回dummy的下一个，即开头的node就可以了。
ListNode dummy = new ListNode(-1);
ListNode current = dummy;
while (!pq.isEmpty()) {
current.next = pq.poll();
current = current.next;
if (current.next != null) {
pq.add(current.next);
current.next = null;
}
}
return dummy.next;
完整的code
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
public ListNode mergeKLists(List<ListNode> lists) {
if (lists == null || lists.size() == 0) {
return null;
}
Queue<ListNode> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
for (ListNode list : lists) {
if (list != null) {
pq.add(list);
}
}
ListNode dummy = new ListNode(-1);
ListNode current = dummy;
while (!pq.isEmpty()) {
current.next = pq.poll();
current = current.next;
if (current.next != null) {
pq.add(current.next);
current.next = null;
}
}
return dummy.next;
}
}
解2
还可以用类似MergeSort的方式来做。每两个merge一个，然后产生一个新的list，再循环新的list，直到只剩一个（即MergeSort bottom up）。
完整的code
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
public ListNode mergeKLists(List<ListNode> lists) {
if (lists == null || lists.size() == 0) {
return null;
}
while (lists.size() != 1) {
List<ListNode> newLists = new ArrayList<>();
for (int i = 0; i + 1 < lists.size(); i+=2) {
ListNode mergedList = merge(lists.get(i), lists.get(i + 1));
newLists.add(mergedList);
}
if (lists.size() % 2 == 1) {
newLists.add(lists.get(lists.size() - 1));
}
lists = newLists;
}
return lists.get(0);
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
while (l1 != null) {
current.next = l1;
l1 = l1.next;
current = current.next;
}
while (l2 != null) {
current.next = l2;
l2 = l2.next;
current = current.next;
}
return dummy.next;
}
}
解3
同样是merge，还可以用divide&conquer来做。merge左半边，再merge右半边，把两边最后再merge，跟MergeSort Top Down的想法是一样的。
完整的code
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
public ListNode mergeKLists(List<ListNode> lists) {
if (lists == null || lists.size() == 0) {
return null;
}
return mergeKHelper(lists, 0, lists.size() - 1);
}
private ListNode mergeKHelper(List<ListNode> lists, int start, int end) {
if (start == end) {
return lists.get(start);
}
int mid = start + (end - start) / 2;
ListNode left = mergeKHelper(lists, start, mid);
ListNode right = mergeKHelper(lists, mid + 1, end);
return merge(left, right);
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
while (l1 != null) {
current.next = l1;
l1 = l1.next;
current = current.next;
}
while (l2 != null) {
current.next = l2;
l2 = l2.next;
current = current.next;
}
return dummy.next;
}
}
分析
时间复杂度
第一个方法，把k个list放进去要O(k)，把总共n个node拿出来每个要O(logk)，所以是O(nlogk)。第二个和第三个方法，都是使用类似于MergeSort的方法，排序总共n个数，每次把k个list平分，所以就是O(nlogk)。
空间复杂度
第一个方法是O(k)的复杂度。MergeSort是O(n)，因为它一直需要一个merge好的list/sublists。
总的来说，PriorityQueue更好一些吧。无论从时间，空间，实现的难易度来说，都是用PriorityQueue来做比较好。不过其它的也要会。
网友评论