原题
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入：
[
1->4->5,
1->3->4,
2->6
] 输出： 1->1->2->3->4->4->5->6
解法
思想
逐一比较或两两合并（分治）。
代码
逐一比较： 时间复杂度O(nm)（n为链表个数，m为链表最大长度）
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode head = new ListNode(0);
ListNode cur = head;
int min = -1;
int leftCount = lists.length;
while(leftCount>0){
for(int i = 0;i<leftCount;i++){
if(lists[i]!=null&&(min==-1||lists[i].val<lists[min].val)) min = i;
}
if(min == -1){
leftCount--;
break;
}
ListNode node = lists[min];
if(lists[min].next==null){
lists[min]=lists[leftCount-1];
leftCount--;
}else lists[min] = lists[min].next;
cur.next = node;
cur = cur.next;
min = -1;
}
return head.next;
}
}
两两合并：时间复杂度O(nm/2)（n为链表个数，m为链表最大长度）
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int len = lists.length;
if (len == 0) {
return null;
}
// 将n个链表以中间为对称，合并
while(len>1) {
for (int i=0; i<len/2; i++) {
lists[i] = mergeTwoListsForK(lists[i], lists[len-1-i]);
}
len = (len+1)/2;
}
return lists[0];
}
private ListNode mergeTwoListsForK(ListNode l1, ListNode l2) {
ListNode head = new ListNode(-1);
ListNode p = head;
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;
} else if (l2 != null) {
p.next = l2;
}
return head.next;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode23-%e5%90%88%e5%b9%b6k%e4%b8%aa%e6%8e%92%e5%ba%8f%e9%93%be%e8%a1%a8/
