前言:
而今小伙伴们对“快速合并算法”大致比较着重,兄弟们都想要学习一些“快速合并算法”的相关文章。那么小编在网摘上汇集了一些有关“快速合并算法””的相关资讯,希望同学们能喜欢,看官们快快来学习一下吧!一、题目
合并 k 个排序链表,返回合并后的排序链表。
二、思路
分治法
三、实现
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
if (lists.length == 1) {
return lists[0];
}
if (lists.length == 2) {
return mergeTwoList(lists[0], lists[1]);
}
int mid = lists.length / 2;
ListNode[] l1 = new ListNode[mid];
for (int i = 0; i < mid; i++) {
l1[i] = lists[i];
}
ListNode[] l2 = new ListNode[lists.length - mid];
for (int i = mid, j = 0; i < lists.length; i++, j++) {
l2[j] = lists[i];
}
return mergeTwoList(mergeKLists(l1), mergeKLists(l2));
}
public ListNode mergeTwoList(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode head = null;
if (l1.val <= l2.val) {
head = l1;
head.next = mergeTwoList(l1.next, l2);
} else {
head = l2;
head.next = mergeTwoList(l1, l2.next);
}
return head;
}
标签: #快速合并算法