Description
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Solution
Divide&conquer
没啥好说的，使用归并思想两两merge。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return mergeKLists(lists, 0, lists.length - 1);
}
public ListNode mergeKLists(ListNode[] lists, int start, int end) {
if (start > end) {
return null;
}
if (start == end) {
return lists[start];
}
int mid = (start + end) >> 1;
ListNode p = mergeKLists(lists, start, mid);
ListNode q = mergeKLists(lists, mid + 1, end);
return mergeSortedList(p, q);
}
public ListNode mergeSortedList(ListNode p, ListNode q) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (p != null && q != null) {
if (p.val <= q.val) {
tail.next = p;
p = p.next;
} else {
tail.next = q;
q = q.next;
}
tail = tail.next;
}
if (p != null) {
tail.next = p;
} else {
tail.next = q;
}
return dummy.next;
}
}
MinHeap
我不懂收益何在啊...TBD
