Merge k Sorted Lists

Question

" class="reference-link">题解1 - 选择归并(TLE)

参考 Merge Two Sorted Lists | Data Structure and Algorithm 中对两个有序链表的合并方法，这里我们也可以采用从 k 个链表中选择其中最小值的节点链接到lastNode->next(和选择排序思路有点类似)，同时该节点所在的链表表头节点往后递推一个。直至lastNode遍历完 k 个链表的所有节点，此时表头节点均为NULL, 返回dummy->next.

这种方法非常简单直接，但是时间复杂度较高，容易出现 TLE.

C++

  1. /**
  2.  * Definition of ListNode
  3.  * class ListNode {
  4.  * public:
  5.  *     int val;
  6.  *     ListNode *next;
  7.  *     ListNode(int val) {
  8.  *         this->val = val;
  9.  *         this->next = NULL;
  10.  *     }
  11.  * }
  12.  */
  14. class Solution {
  15. public:
  16.     /**
  17.      * @param lists: a list of ListNode
  18.      * @return: The head of one sorted list.
  19.      */
  20.     ListNode *mergeKLists(vector<ListNode *> &lists) {
  21.         if (lists.empty()) {
  22.             return NULL;
  23.         }
  25.         ListNode *dummy = new ListNode(INT_MAX);
  26.         ListNode *last = dummy;
  28.         while (true) {
  29.             int count = 0;
  30.             int index = -1, tempVal = INT_MAX;
  31.             for (int i = 0; i != lists.size(); ++i) {
  32.                 if (NULL == lists[i]) {
  33.                     ++count;
  34.                     if (count == lists.size()) {
  35.                         last->next = NULL;
  36.                         return dummy->next;
  37.                     }
  38.                     continue;
  39.                 }
  41.                 // choose the min value in non-NULL ListNode
  42.                 if (NULL != lists[i] && lists[i]->val <= tempVal) {
  43.                     tempVal = lists[i]->val;
  44.                     index = i;
  45.                 }
  46.             }
  48.             last->next = lists[index];
  49.             last = last->next;
  50.             lists[index] = lists[index]->next;
  51.         }
  52.     }
  53. };

源码分析

  1. 由于头节点不定，我们使用dummy节点。
  2. 使用last表示每次归并后的新链表末尾节点。
  3. count用于累计链表表头节点为NULL的个数，若与 vector 大小相同则代表所有节点均已遍历完。
  4. tempVal用于保存每次比较 vector 中各链表表头节点中的最小值，index保存本轮选择归并过程中最小值对应的链表索引，用于循环结束前递推该链表表头节点。

复杂度分析

由于每次for循环只能选择出一个最小值，总的时间复杂度最坏情况下为 O(k \cdot \sum ^{k}_{i=1}l_i). 空间复杂度近似为 O(1).

" class="reference-link">题解2 - 迭代调用Merge Two Sorted Lists(TLE)

鉴于题解1时间复杂度较高，题解2中我们可以反复利用时间复杂度相对较低的 Merge Two Sorted Lists | Data Structure and Algorithm. 即先合并链表1和2，接着将合并后的新链表再与链表3合并，如此反复直至 vector 内所有链表均已完全合并[^soulmachine]。

C++

  1. /**
  2.  * Definition of ListNode
  3.  * class ListNode {
  4.  * public:
  5.  *     int val;
  6.  *     ListNode *next;
  7.  *     ListNode(int val) {
  8.  *         this->val = val;
  9.  *         this->next = NULL;
  10.  *     }
  11.  * }
  12.  */
  14. class Solution {
  15. public:
  16.     /**
  17.      * @param lists: a list of ListNode
  18.      * @return: The head of one sorted list.
  19.      */
  20.     ListNode *mergeKLists(vector<ListNode *> &lists) {
  21.         if (lists.empty()) {
  22.             return NULL;
  23.         }
  25.         ListNode *head = lists[0];
  26.         for (int i = 1; i != lists.size(); ++i) {
  27.             head = merge2Lists(head, lists[i]);
  28.         }
  30.         return head;
  31.     }
  33. private:
  34.     ListNode *merge2Lists(ListNode *left, ListNode *right) {
  35.         ListNode *dummy = new ListNode(0);
  36.         ListNode *last = dummy;
  38.         while (NULL != left && NULL != right) {
  39.             if (left->val < right->val) {
  40.                 last->next = left;
  41.                 left = left->next;
  42.             } else {
  43.                 last->next = right;
  44.                 right = right->next;
  45.             }
  46.             last = last->next;
  47.         }
  49.         last->next = (NULL != left) ? left : right;
  51.         return dummy->next;
  52.     }
  53. };

源码分析

实现合并两个链表的子方法后就没啥难度了，mergeKLists中左半部分链表初始化为lists[0], for循环后迭代归并head和lists[i].

复杂度分析

合并两个链表时最差时间复杂度为 O(l1+l_2), 那么在以上的实现中总的时间复杂度可近似认为是 l_1 + l_1+l_2 +…+l_1+l_2+…+l_k = O(\sum {i=1} ^{k} (k-i) \cdot l_i). 比起题解1复杂度是要小一点，但量级上仍然差不太多。实际运行时间也证明了这一点，题解2的运行时间差不多时题解1的一半。那么还有没有进一步降低时间复杂度的可能呢？当然是有的，且看下题分解…

题解3 - 二分调用Merge Two Sorted Lists

题解2中merge2Lists优化空间不大，那咱们就来看看mergeKLists中的for循环，仔细观察可得知第i个链表 li 被遍历了 k-i 次，如果我们使用二分法对其进行归并呢？从中间索引处进行二分归并后，每个链表参与合并的次数变为 \log k, 故总的时间复杂度可降至 \log k \cdot \sum {i=1} ^{k} l_i. 优化幅度较大。

C++

  1. /**
  2.  * Definition of ListNode
  3.  * class ListNode {
  4.  * public:
  5.  *     int val;
  6.  *     ListNode *next;
  7.  *     ListNode(int val) {
  8.  *         this->val = val;
  9.  *         this->next = NULL;
  10.  *     }
  11.  * }
  12.  */
  14. class Solution {
  15. public:
  16.     /**
  17.      * @param lists: a list of ListNode
  18.      * @return: The head of one sorted list.
  19.      */
  20.     ListNode *mergeKLists(vector<ListNode *> &lists) {
  21.         if (lists.empty()) {
  22.             return NULL;
  23.         }
  25.         return helper(lists, 0, lists.size() - 1);
  26.     }
  28. private:
  29.     ListNode *helper(vector<ListNode *> &lists, int start, int end) {
  30.         if (start == end) {
  31.             return lists[start];
  32.         } else if (start + 1 == end) {
  33.             return merge2Lists(lists[start], lists[end]);
  34.         }
  36.         ListNode *left = helper(lists, start, start + (end - start) / 2);
  37.         ListNode *right = helper(lists, start + (end - start) / 2 + 1, end);
  39.         return merge2Lists(left, right);
  40.     }
  42.     ListNode *merge2Lists(ListNode *left, ListNode *right) {
  43.         ListNode *dummy = new ListNode(0);
  44.         ListNode *last = dummy;
  46.         while (NULL != left && NULL != right) {
  47.             if (left->val < right->val) {
  48.                 last->next = left;
  49.                 left = left->next;
  50.             } else {
  51.                 last->next = right;
  52.                 right = right->next;
  53.             }
  54.             last = last->next;
  55.         }
  56.         last->next = (NULL != left) ? left : right;
  58.         return dummy->next;
  59.     }
  60. };

源码分析

由于需要建立二分递归模型，另建一私有方法helper引入起止位置较为方便。下面着重分析helper。

  1. 分两种边界条件处理，分别是start == end和start + 1 == end. 虽然第二种边界条件可以略去，但是加上会节省递归调用的栈空间。
  2. 使用分治思想理解helper, left和right的边界处理建议先分析几个简单例子，做到不重不漏。
  3. 注意merge2Lists中传入的参数，为lists[start]而不是start…

在mergeKLists中调用helper时传入的end参数为lists.size() - 1，而不是lists.size().

复杂度分析

题解中已分析过，最坏的时间复杂度为 \log k \cdot \sum _{i=1} ^{k} l_i, 空间复杂度近似为 O(1).

优化后的运行时间显著减少！由题解2中的500+ms 减至40ms 以内。

Reference