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. class Solution {
  5. public:
  6.     ListNode *mergeKLists(vector &lists) {
  7.         if (lists.size() == 0) return nullptr;
  9.         ListNode *p = lists[0];
  10.         for (int i = 1; i < lists.size(); i++) {
  11.             p = mergeTwoLists(p, lists[i]);
  12.         }
  13.         return p;
  14.     }
  16.     // Merge Two Sorted Lists
  17.     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
  18.         ListNode head(-1);
  19.         for (ListNode* p = &head; l1 != nullptr || l2 != nullptr; p = p->next) {
  20.             int val1 = l1 == nullptr ? INT_MAX : l1->val;
  21.             int val2 = l2 == nullptr ? INT_MAX : l2->val;
  22.             if (val1 next = l1;
  23.                 l1 = l1->next;
  24.             } else {
  25.                 p->next = l2;
  26.                 l2 = l2->next;
  27.             }
  28.         }
  29.         return head.next;
  30.     }
  31. };

相关题目

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