题目
难度： 困难
描述：
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
思路
时间复杂度分析：因为允许k的长度为10^4，所以O(n2)是肯定过不去的，可以使用O(nlogn)或者更低,提示中标红处是我们需要注意的地方
解法思路：本题我使用的是暴力解法，首先先将这个链表集合中的所有元素进行合并，生成一个长的链表，因为子链表的长度在500范围内，所以时间复杂度最终会是O(n)，同时使用快速排序进行排序，最终时间复杂度在O(nlogn)
代码
先将链表集合中的所有子链表合成一条链表：
public static ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
ListNode dummy = new ListNode(-1);
ListNode tail = dummy;
for(int i =0;i<k;i++){
while(lists[i] != null){
ListNode temp = lists[i];
lists[i] = lists[i].next;
tail.next= temp;
tail = tail.next;
}
}
return quickSort(dummy.next);
}
然后对链表进行快速排序：
快速排序思路：设置一个中间值，将小于该值的数放在左边，大于的放在右边
针对本题：设置三个链表，一个存储小于的值，一个存储等于的值，一个存储大于的值
public static ListNode quickSort(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode pivot = head;
ListNode lessHead = new ListNode(-1);
ListNode lessTail = lessHead;
ListNode biggerHead = new ListNode(-1);
ListNode biggerTail = biggerHead;
ListNode equalHead = new ListNode(-1);
ListNode equalTail = equalHead;
ListNode current = head;
while(current != null){
if(current.val < pivot.val){
lessTail.next = current;
lessTail=lessTail.next;
}else if(current.val > pivot.val){
biggerTail.next = current;
biggerTail = biggerTail.next;
}else{
equalTail.next = current;
equalTail = equalTail.next;
}
current = current.next;
}
lessTail.next =null;
biggerTail.next =null;
equalTail.next = null;
ListNode sortedLess = quickSort(lessHead.next);
ListNode sortedBigger = quickSort(biggerHead.next);
return concer(sortedLess,equalHead.next,sortedBigger);
}
然后分别从小到大，依此添加到链表中：
public static ListNode concer(ListNode less,ListNode euqal,ListNode bigger){
ListNode dummyhead = new ListNode(-1);
ListNode tail = dummyhead;
tail.next = less;
tail = getTail(tail);
tail.next =euqal ;
tail = getTail(tail);
tail.next = bigger;
return dummyhead.next;
}
public static ListNode getTail(ListNode head){
if(head == null){
return null;
}
while(head.next != null){
head = head.next;
}
return head;
}
我这里使用了最简单的方法，还有很多优质的解法，可以参考力扣中大神的做法。
完整代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
//暴力解法
public static ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
ListNode dummy = new ListNode(-1);
ListNode tail = dummy;
for(int i =0;i<k;i++){
while(lists[i] != null){
ListNode temp = lists[i];
lists[i] = lists[i].next;
tail.next= temp;
tail = tail.next;
}
}
return quickSort(dummy.next);
}
public static ListNode quickSort(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode pivot = head;
ListNode lessHead = new ListNode(-1);
ListNode lessTail = lessHead;
ListNode biggerHead = new ListNode(-1);
ListNode biggerTail = biggerHead;
ListNode equalHead = new ListNode(-1);
ListNode equalTail = equalHead;
ListNode current = head;
while(current != null){
if(current.val < pivot.val){
lessTail.next = current;
lessTail=lessTail.next;
}else if(current.val > pivot.val){
biggerTail.next = current;
biggerTail = biggerTail.next;
}else{
equalTail.next = current;
equalTail = equalTail.next;
}
current = current.next;
}
lessTail.next =null;
biggerTail.next =null;
equalTail.next = null;
ListNode sortedLess = quickSort(lessHead.next);
ListNode sortedBigger = quickSort(biggerHead.next);
return concer(sortedLess,equalHead.next,sortedBigger);
}
public static ListNode concer(ListNode less,ListNode euqal,ListNode bigger){
ListNode dummyhead = new ListNode(-1);
ListNode tail = dummyhead;
tail.next = less;
tail = getTail(tail);
tail.next =euqal ;
tail = getTail(tail);
tail.next = bigger;
return dummyhead.next;
}
public static ListNode getTail(ListNode head){
if(head == null){
return null;
}
while(head.next != null){
head = head.next;
}
return head;
}
}