算法 【leetcode热题100】合并K个排序链表

难度： 困难

通过率： 31.9%

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:

[

  1->4->5,

  1->3->4,

  2->6

]

输出: 1->1->2->3->4->4->5->6

解法一 暴力破解

简单粗暴，遍历所有的链表，将数字存到一个数组里，然后用快速排序，最后再将排序好的数组存到一个链表里。

public ListNode mergeKLists(ListNode[] lists) {

List l = new ArrayList();

//存到数组

for (ListNode ln : lists) {

while (ln != null) {

l.add(ln.val);

ln = ln.next;

}

}

//数组排序

Collections.sort(l);

//存到链表

ListNode head = new ListNode(0);

ListNode h = head;

for (int i : l) {

ListNode t = new ListNode(i);

h.next = t;

h = h.next;

}

h.next = null;

return head.next;

}

时间复杂度：假设 N 是所有的数字个数，存到数组是 O（N），排序如果是用快速排序就是 O(Nlog​N​​) ，存到链表是 O（N），所以取个最大的，就是 O(Nlog​N​​)。

空间复杂度：新建了一个链表，O（N）。

解法二 一列一列比较

我们可以一列一列的比较，将最小的一个存到一个新的链表里。

public ListNode

相关阅读

 您阅读本篇文章共花了：