Merge k Sorted Lists · 數據結構與算法/leetcode/lintcode題解

# Merge k Sorted Lists ### Source - leetcode: [Merge k Sorted Lists | LeetCode OJ](https://leetcode.com/problems/merge-k-sorted-lists/) - lintcode: [(104) Merge k Sorted Lists](http://www.lintcode.com/en/problem/merge-k-sorted-lists/) ### 題解1 - 選擇歸并([TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。")) 參考 [Merge Two Sorted Lists | Data Structure and Algorithm](http://algorithm.yuanbin.me/zh-cn/linked_list/merge_two_sorted_lists.html) 中對兩個有序鏈表的合并方法，這里我們也可以采用從 k 個鏈表中選擇其中最小值的節點鏈接到`lastNode->next`(和選擇排序思路有點類似)，同時該節點所在的鏈表表頭節點往后遞推一個。直至`lastNode`遍歷完 k 個鏈表的所有節點，此時表頭節點均為`NULL`, 返回`dummy->next`. 這種方法非常簡單直接，但是時間復雜度較高，容易出現 [TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。"). ### C++ ~~~ /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param lists: a list of ListNode * @return: The head of one sorted list. */ ListNode *mergeKLists(vector<ListNode *> &lists) { if (lists.empty()) { return NULL; } ListNode *dummy = new ListNode(INT_MAX); ListNode *last = dummy; while (true) { int count = 0; int index = -1, tempVal = INT_MAX; for (int i = 0; i != lists.size(); ++i) { if (NULL == lists[i]) { ++count; if (count == lists.size()) { last->next = NULL; return dummy->next; } continue; } // choose the min value in non-NULL ListNode if (NULL != lists[i] && lists[i]->val <= tempVal) { tempVal = lists[i]->val; index = i; } } last->next = lists[index]; last = last->next; lists[index] = lists[index]->next; } } }; ~~~ ### 源碼分析 1. 由于頭節點不定，我們使用`dummy`節點。 1. 使用`last`表示每次歸并后的新鏈表末尾節點。 1. `count`用于累計鏈表表頭節點為`NULL`的個數，若與 vector 大小相同則代表所有節點均已遍歷完。 1. `tempVal`用于保存每次比較 vector 中各鏈表表頭節點中的最小值，`index`保存本輪選擇歸并過程中最小值對應的鏈表索引，用于循環結束前遞推該鏈表表頭節點。 ### 復雜度分析由于每次`for`循環只能選擇出一個最小值，總的時間復雜度最壞情況下為 O(k?∑i=1kli)O(k \cdot \sum ^{k}_{i=1}l_i)O(k?∑i=1kli). 空間復雜度近似為 O(1)O(1)O(1). ### 題解2 - 迭代調用`Merge Two Sorted Lists`([TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。")) 鑒于題解1時間復雜度較高，題解2中我們可以反復利用時間復雜度相對較低的 [Merge Two Sorted Lists | Data Structure and Algorithm](http://algorithm.yuanbin.me/zh-cn/linked_list/merge_two_sorted_lists.html). 即先合并鏈表1和2，接著將合并后的新鏈表再與鏈表3合并，如此反復直至 vector 內所有鏈表均已完全合并[soulmachine](#)。 ### C++ ~~~ /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param lists: a list of ListNode * @return: The head of one sorted list. */ ListNode *mergeKLists(vector<ListNode *> &lists) { if (lists.empty()) { return NULL; } ListNode *head = lists[0]; for (int i = 1; i != lists.size(); ++i) { head = merge2Lists(head, lists[i]); } return head; } private: ListNode *merge2Lists(ListNode *left, ListNode *right) { ListNode *dummy = new ListNode(0); ListNode *last = dummy; while (NULL != left && NULL != right) { if (left->val < right->val) { last->next = left; left = left->next; } else { last->next = right; right = right->next; } last = last->next; } last->next = (NULL != left) ? left : right; return dummy->next; } }; ~~~ ### 源碼分析實現合并兩個鏈表的子方法后就沒啥難度了，`mergeKLists`中左半部分鏈表初始化為`lists[0]`, `for`循環后迭代歸并`head`和`lists[i]`. ### 復雜度分析合并兩個鏈表時最差時間復雜度為 O(l1+l2)O(l_1+l_2)O(l1+l2), 那么在以上的實現中總的時間復雜度可近似認為是 l1+l1+l2+...+l1+l2+...+lk=O(∑i=1k(k?i)?li)l_1 + l_1+l_2 +...+l_1+l_2+...+l_k = O(\sum _{i=1} ^{k} (k-i) \cdot l_i)l1+l1+l2+...+l1+l2+...+lk=O(∑i=1k(k?i)?li). 比起題解1復雜度是要小一點，但量級上仍然差不太多。實際運行時間也證明了這一點，題解2的運行時間差不多時題解1的一半。那么還有沒有進一步降低時間復雜度的可能呢？當然是有的，且看下題分解... ### 題解3 - 二分調用`Merge Two Sorted Lists` 題解2中`merge2Lists`優化空間不大，那咱們就來看看`mergeKLists`中的`for`循環，仔細觀察可得知第`i`個鏈表 lil_ili 被遍歷了 k?ik-ik?i 次，如果我們使用二分法對其進行歸并呢？從中間索引處進行二分歸并后，每個鏈表參與合并的次數變為 logk\log klogk, 故總的時間復雜度可降至 logk?∑i=1kli\log k \cdot \sum _{i=1} ^{k} l_ilogk?∑i=1kli. 優化幅度較大。 ### C++ ~~~ /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param lists: a list of ListNode * @return: The head of one sorted list. */ ListNode *mergeKLists(vector<ListNode *> &lists) { if (lists.empty()) { return NULL; } return helper(lists, 0, lists.size() - 1); } private: ListNode *helper(vector<ListNode *> &lists, int start, int end) { if (start == end) { return lists[start]; } else if (start + 1 == end) { return merge2Lists(lists[start], lists[end]); } ListNode *left = helper(lists, start, start + (end - start) / 2); ListNode *right = helper(lists, start + (end - start) / 2 + 1, end); return merge2Lists(left, right); } ListNode *merge2Lists(ListNode *left, ListNode *right) { ListNode *dummy = new ListNode(0); ListNode *last = dummy; while (NULL != left && NULL != right) { if (left->val < right->val) { last->next = left; left = left->next; } else { last->next = right; right = right->next; } last = last->next; } last->next = (NULL != left) ? left : right; return dummy->next; } }; ~~~ ### 源碼分析由于需要建立二分遞歸模型，另建一私有方法`helper`引入起止位置較為方便。下面著重分析`helper`。 1. 分兩種邊界條件處理，分別是`start == end`和`start + 1 == end`. 雖然第二種邊界條件可以略去，但是加上會節省遞歸調用的棧空間。 1. 使用分治思想理解`helper`, `left`和`right`的邊界處理建議先分析幾個簡單例子，做到不重不漏。 1. 注意`merge2Lists`中傳入的參數，為`lists[start]`而不是`start`... 在`mergeKLists`中調用`helper`時傳入的`end`參數為`lists.size() - 1`，而不是`lists.size()`. ### 復雜度分析題解中已分析過，最壞的時間復雜度為 logk?∑i=1kli\log k \cdot \sum _{i=1} ^{k} l_ilogk?∑i=1kli, 空間復雜度近似為 O(1)O(1)O(1). 優化后的運行時間顯著減少！由題解2中的500+ms 減至40ms 以內。 ### Reference - soulmachine > . [soulmachine的LeetCode 題解](#)[ ?](# "Jump back to footnote [soulmachine] in the text.")