Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
https://oj.leetcode.com/problems/merge-k-sorted-lists/
思路1（naive）：1跟2合并，然后跟3合并，然后跟4合并，一直到k个合并完。
复杂度：1,2合并访问2n个节点，12与3合并访问3n个节点，...，123~k-1与k合并访问kn个节点，总共遍历节点数目n(3+4+5+...+k)，O(nk^2)。
思路2：mergeSort的思想，K个链表先划分为合并两个k/2的链表，每个k/2的链表在划分为k/4的链表，一直到只剩一个或者两个链表。
复杂度：T(k)=2T(k/2)+O(nk)，根据 主定理（算法导论上有讲），复杂度为O(nklogk)。
思路3：维护一个大小为k的堆。每次取堆顶元素放到结果中，并把该元素的后继（如果有）放入堆中。
复杂度：每个元素读取一次nk，堆操作logk，所以复杂度为O(nklogk)。
思路2代码：
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists == null)
return null;
return merge(lists, 0, lists.size() - 1);
}
private ListNode merge(ArrayList<ListNode> lists, int start, int end) {
if (start == end)
return lists.get(start);
int mid = (start + end) / 2;
ListNode one = merge(lists, start, mid);
ListNode two = merge(lists, mid + 1, end);
return mergeTwoLists(one, two);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null)
return l2;
if (l2 == null)
return l1;
ListNode p1 = l1;
ListNode p2 = l2;
ListNode head = new ListNode(-1);
head.next = p1.val <= p2.val ? p1 : p2;
ListNode tail = head;
while (p1 != null && p2 != null) {
if (p1.val <= p2.val) {
tail.next = p1;
ListNode oldP1 = p1;
p1 = p1.next;
oldP1.next = null;
tail = oldP1;
} else {
tail.next = p2;
ListNode oldP2 = p2;
p2 = p2.next;
oldP2.next = null;
tail = oldP2;
}
}
if (p1 != null)
tail.next = p1;
if (p2 != null)
tail.next = p2;
return head.next;
}
思路3代码（加测试代码）：
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists == null)
return null;
PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(20, new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
});
ListNode head = new ListNode(-1);
ListNode cur = head;
for (int i = 0; i < lists.size(); i++) {
if (lists.get(i) != null)
pq.add(lists.get(i));
}
while (!pq.isEmpty()) {
ListNode out = pq.remove();
cur.next = out;
cur = cur.next;
if (out.next != null)
pq.add(out.next);
}
return head.next;
}
public static void main(String[] args) {
ArrayList<ListNode> lists = new ArrayList<ListNode>();
int k = 3;
for (int i = 0; i < k; i++) {
ListNode list = makeList(getRandomArray());
lists.add(list);
printList(list);
}
printList(new Solution().mergeKLists(lists));
}
private static int[] getRandomArray() {
Random rand = new Random();
int size = rand.nextInt(10);
int[] res = new int[size];
if (size == 0)
return res;
res[size - 1] = 100;
for (int i = size - 2; i >= 0; i--) {
res[i] = rand.nextInt(res[i + 1] + 1);
}
return res;
}
private static ListNode makeList(int[] a) {
ListNode head = new ListNode(-1);
ListNode p = head;
for (int i = 0; i < a.length; i++) {
p.next = new ListNode(a[i]);
p = p.next;
}
return head.next;
}
private static void printList(ListNode head) {
while (head != null) {
System.out.print(head.val);
if (head.next != null)
System.out.print("->");
head = head.next;
}
System.out.println();
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
第二遍记录：
归并法：注意cornor case，lists==null or lists.size()==0.
public class Solution { public ListNode mergeKLists(List<ListNode> lists) { if(lists==null||lists.size()==0) return null; return merge(lists,0,lists.size()-1); } private ListNode merge(List<ListNode> lists, int start, int end){ if(start>=end){ return lists.get(start); } int mid = (start+end)/2; ListNode one = merge(lists,start,mid); ListNode two = merge(lists,mid+1,end); return mergeTwoLists(one,two); } private ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1==null) return l2; if(l2==null) return l1; ListNode dummyHead = new ListNode(-1); ListNode p =dummyHead; while(l1!=null&&l2!=null){ if(l1.val<=l2.val){ p.next =l1; l1=l1.next; } else{ p.next=l2; l2=l2.next; } p=p.next; } if(l1!=null) p.next=l1; if(l2!=null) p.next=l2; return dummyHead.next; } }
用PriorityQueue的方法，注意自定义Comparator。
public class Solution { public ListNode mergeKLists(List<ListNode> lists) { if(lists==null) return null; PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(20, new Comparator<ListNode>(){ @Override public int compare(ListNode a, ListNode b){ return a.val-b.val; } }); ListNode dummyHead = new ListNode(-1); for(int i=0;i<lists.size();i++){ ListNode head = lists.get(i); if(head!=null) pq.add(head); } ListNode cur = dummyHead; while(!pq.isEmpty()){ ListNode out = pq.remove(); cur.next = out; cur = cur.next; if(out.next!=null) pq.add(out.next); } return dummyHead.next; } }
参考：