Merge k Sorted Lists

描述

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

分析

可以复用 Merge Two Sorted Lists 的函数

代码

  1. // Merge k Sorted Lists
  2. // 时间复杂度O(n1+n2+...)，空间复杂度O(1)
  3. // TODO: 会超时
  4. public class Solution {
  5.     public ListNode mergeKLists(ListNode[] lists) {
  6.         if (lists.length == 0) return null;
  8.         ListNode p = lists[0];
  9.         for (int i = 1; i < lists.length; i++) {
  10.             p = mergeTwoLists(p, lists[i]);
  11.         }
  12.         return p;
  13.     }
  15.     // Merge Two Sorted Lists
  16.     ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  17.         ListNode head = new ListNode(-1);
  18.         for (ListNode p = head; l1 != null || l2 != null; p = p.next) {
  19.             int val1 = l1 == null ? Integer.MAX_VALUE : l1.val;
  20.             int val2 = l2 == null ? Integer.MAX_VALUE : l2.val;
  21.             if (val1

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/sorting/merge-sort/merge-k-sorted-lists.html