自己解法
合并K个有序列表，和21题合并两个有序链表思路类似，这个题最开始想偏了，想比较每个链表的头结点，然后后移这种多路归并，发现很难操作。
使用分治的思想，将链表两两合并，直到最后只剩一条链表就搞定了。条数为奇数时，需要处理下，会余下一个链表没人合，需要直接填入。时间复杂度为O(NlogK),空间复杂度为O(N)
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
if (lists.length == 1) {
return lists[0];
}
int newLength = lists.length % 2 == 1 ? lists.length / 2 + 1 : lists.length / 2;
ListNode[] res = new ListNode[newLength];
int j = 0;
int i = 0;
for (; i < lists.length - 1; i++) {
ListNode l = mergeTwoLists(lists[i], lists[++i]);
res[j++] = l;
}
if (i == lists.length - 1) {
res[j] = lists[i];
}
return mergeKLists(res);
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode res = new ListNode(-1);
ListNode temp = res;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
temp.next = new ListNode(l1.val);
temp = temp.next;
l1 = l1.next;
} else {
temp.next = new ListNode(l2.val);
temp = temp.next;
l2 = l2.next;
}
}
temp.next = l1 != null ? l1 : l2;
return res.next;
}
}
别人解法
先贴一种最小堆解法,这种是自己最开始的思路，但没想好怎么维护最小的头部节点，时间复杂度为O（NlogK）。
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
for (ListNode node: lists) {
if (node != null) {
pq.offer(node);
}
}
ListNode dummyHead = new ListNode(0);
ListNode tail = dummyHead;
while (!pq.isEmpty()) {
ListNode minNode = pq.poll();
tail.next = minNode;
tail = minNode;
if (minNode.next != null) {
pq.offer(minNode.next);
}
}
return dummyHead.next;
}
}
再贴一种两两合并的解法，因为自己用的是迭代，贴种递归的，递归确实还是不太熟。
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
return merge(lists, 0, lists.length - 1);
}
private ListNode merge(ListNode[] lists, int lo, int hi) {
if (lo == hi) {
return lists[lo];
}
int mid = lo + (hi - lo) / 2;
ListNode l1 = merge(lists, lo, mid);
ListNode l2 = merge(lists, mid + 1, hi);
return merge2Lists(l1, l2);
}
}
网友评论