Merge k Sorted Lists (H)
題目
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
題意
將k個有序鏈表合并為一個有序鏈表，
思路
與二路歸并類似的方法，但可以利用優先佇列來找k個結點中的最小結點，
也可以將所有鏈表分為若干個小組，每次都進行二路歸并，最后歸并成一個大鏈表，
兩種方法的時間復雜度都為\(O(Nlogk)\)，但實際提交后運行時間相差較大，分析原因可能在于：優先佇列法中，每一個結點都需要單獨連接到新鏈表后，而分治法中，當兩個鏈表中其中一個為null時，可以將另一個鏈表中剩余的結點直接連接到新鏈表后，省去了一部分時間，
代碼實作
Java
優先佇列
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode dummy = new ListNode();
ListNode cur = dummy;
Queue<ListNode> q = new PriorityQueue<>((x, y) -> x.val - y.val);
for (ListNode head : lists) {
if (head != null) {
q.offer(head);
}
}
while (!q.isEmpty()) {
cur.next = q.poll();
cur = cur.next;
if (cur.next != null) {
q.offer(cur.next);
}
}
return dummy.next;
}
}
分治法
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 特殊情況先排除，不然陣列下標會溢位
if (lists.length == 0) {
return null;
}
for (int step = 1; step < lists.length; step *= 2) {
for (int i = 0; i + step < lists.length; i += 2 * step) {
lists[i] = mergeTwo(lists[i], lists[i + step]);
}
}
return lists[0];
}
private ListNode mergeTwo(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode pointer = head;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
pointer.next = l1;
l1 = l1.next;
} else {
pointer.next = l2;
l2 = l2.next;
}
pointer = pointer.next;
}
pointer.next = l1 == null ? l2 : l1;
return head.next;
}
}
JavaScript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function (lists) {
if (lists.length === 0) {
return null
}
for (let step = 1; step < lists.length; step *= 2) {
for (let i = 0; i + step < lists.length; i += step * 2) {
lists[i] = merge(lists[i], lists[i + step])
}
}
return lists[0]
}
let merge = function (list1, list2) {
let dummy = new ListNode()
let cur = dummy
while (list1 !== null && list2 !== null) {
if (list1.val < list2.val) {
cur.next = list1
list1 = list1.next
} else {
cur.next = list2
list2 = list2.next
}
cur = cur.next
}
cur.next = list1 ? list1 : list2
return dummy.next
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/41147.html
標籤：其他