龙空技术网

算法题:合并k个有序链表

加班狗的微博 98

前言:

而今小伙伴们对“快速合并算法”大致比较着重,兄弟们都想要学习一些“快速合并算法”的相关文章。那么小编在网摘上汇集了一些有关“快速合并算法””的相关资讯,希望同学们能喜欢,看官们快快来学习一下吧!

一、题目

合并 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;

}

标签: #快速合并算法