題目
合并 k 個排序鏈表，返回合并后的排序鏈表。請分析和描述算法的復(fù)雜度。
示例:
輸入:
[
1->4->5,
1->3->4,
2->6
]
輸出: 1->1->2->3->4->4->5->6
思路
- 使用優(yōu)先隊(duì)列并實(shí)現(xiàn)comparator接口
- 開辟帶有頭節(jié)點(diǎn)的新鏈表foo
- 當(dāng)隊(duì)列不為空時挡鞍，將最小鏈表出隊(duì)并與foo建立關(guān)聯(lián)，將foo后移 预烙，如果不為空則將foo的第二個及后續(xù)節(jié)點(diǎn)放入隊(duì)列中再次循環(huán)
- 當(dāng)隊(duì)列為空時墨微，返回foo即為合并后的新鏈表
核心代碼
while (!queue.isEmpty()) {
cur.next = queue.poll();//將較小的出隊(duì)并建立關(guān)聯(lián)
cur = cur.next;//從頭節(jié)點(diǎn)移到首節(jié)點(diǎn)
if (cur.next != null) {
queue.add(cur.next);//將第二個節(jié)點(diǎn)及以后節(jié)點(diǎn)重新放入隊(duì)列中
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
for (ListNode list : lists) {
if (list != null) {
queue.add(list);
}
}
while (!queue.isEmpty()) {
cur.next = queue.poll();//將較小的出隊(duì)并建立關(guān)聯(lián)
cur = cur.next;//從頭節(jié)點(diǎn)移到首節(jié)點(diǎn)
if (cur.next != null) {
queue.add(cur.next);//將第二個節(jié)點(diǎn)及以后節(jié)點(diǎn)重新放入隊(duì)列中
}
}
return dummy.next;
}
}
