題目
合并 K 個(gè)升序鏈表
難度： 困難
描述：
給你一個(gè)鏈表數(shù)組，每個(gè)鏈表都已經(jīng)按升序排列。
請你將所有鏈表合并到一個(gè)升序鏈表中，返回合并后的鏈表。
示例 1：
輸入：lists = [[1,4,5],[1,3,4],[2,6]]
輸出：[1,1,2,3,4,4,5,6]
解釋：鏈表數(shù)組如下：
[
1->4->5,
1->3->4,
2->6
]
將它們合并到一個(gè)有序鏈表中得到。
1->1->2->3->4->4->5->6
示例 2：
輸入：lists = []
輸出：[]
示例 3：
輸入：lists = [[]]
輸出：[]
提示：
k == lists.length
0 <= k <= 10^40 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的總和不超過 10^4
思路
時(shí)間復(fù)雜度分析：因?yàn)樵试Sk的長度為10^4，所以O(shè)(n2)是肯定過不去的，可以使用O(nlogn)或者更低,提示中標(biāo)紅處是我們需要注意的地方
解法思路：本題我使用的是暴力解法，首先先將這個(gè)鏈表集合中的所有元素進(jìn)行合并，生成一個(gè)長的鏈表，因?yàn)樽渔湵淼拈L度在500范圍內(nèi)，所以時(shí)間復(fù)雜度最終會是O(n)，同時(shí)使用快速排序進(jìn)行排序，最終時(shí)間復(fù)雜度在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);
}
然后對鏈表進(jìn)行快速排序：
快速排序思路：設(shè)置一個(gè)中間值，將小于該值的數(shù)放在左邊，大于的放在右邊
針對本題：設(shè)置三個(gè)鏈表，一個(gè)存儲小于的值，一個(gè)存儲等于的值，一個(gè)存儲大于的值
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;
}
我這里使用了最簡單的方法，還有很多優(yōu)質(zhì)的解法，可以參考力扣中大神的做法。文章來源：http://www.zghlxwxcb.cn/news/detail-642410.html
完整代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-642410.html
/**
* 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;
}
}
到了這里，關(guān)于【力扣每日一題】23. 合并 K 個(gè)升序鏈表 &暴力法-快排 & 8.12打卡的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
