题目
法1：分治合并
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
public ListNode merge(ListNode[] lists, int l, int r) {
if (l > r) {
return null;
}
if (l == r) {
return lists[l];
}
int mid = l + (r - l) / 2;
return merge2List(merge(lists, l, mid), merge(lists, mid + 1, r));
}
public ListNode merge2List(ListNode first, ListNode second) {
ListNode dummy = new ListNode(-1);
ListNode tmp = dummy;
while (first != null && second != null) {
if (first.val <= second.val) {
tmp.next = first;
first = first.next;
} else {
tmp.next = second;
second = second.next;
}
tmp = tmp.next;
}
if (first == null) {
tmp.next = second;
}
if (second == null) {
tmp.next = first;
}
return dummy.next;
}
}
法2：其他
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
if (lists.length == 1) {
return lists[0];
}
ListNode merged = lists[0];
for (int i = 1; i < lists.length; ++i) {
merged = merge(merged, lists[i]);
}
return merged;
}
public ListNode merge(ListNode first, ListNode second) {
ListNode dummy = new ListNode(-1);
ListNode tmp = dummy;
while (first != null && second != null) {
if (first.val <= second.val) {
tmp.next = first;
first = first.next;
} else {
tmp.next = second;
second = second.next;
}
tmp = tmp.next;
}
if (first == null) {
tmp.next = second;
}
if (second == null) {
tmp.next = first;
}
return dummy.next;
}
}
