# 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 的簡(jiǎn)稱。你的程序在 OJ 上的運(yùn)行時(shí)間太長(zhǎng)了，超過(guò)了對(duì)應(yīng)題目的時(shí)間限制。"))
參考 [Merge Two Sorted Lists | Data Structure and Algorithm](http://algorithm.yuanbin.me/zh-cn/linked_list/merge_two_sorted_lists.html) 中對(duì)兩個(gè)有序鏈表的合并方法，這里我們也可以采用從 k 個(gè)鏈表中選擇其中最小值的節(jié)點(diǎn)鏈接到`lastNode->next`(和選擇排序思路有點(diǎn)類似)，同時(shí)該節(jié)點(diǎn)所在的鏈表表頭節(jié)點(diǎn)往后遞推一個(gè)。直至`lastNode`遍歷完 k 個(gè)鏈表的所有節(jié)點(diǎn)，此時(shí)表頭節(jié)點(diǎn)均為`NULL`, 返回`dummy->next`.
這種方法非常簡(jiǎn)單直接，但是時(shí)間復(fù)雜度較高，容易出現(xiàn) [TLE](# "Time Limit Exceeded 的簡(jiǎn)稱。你的程序在 OJ 上的運(yùn)行時(shí)間太長(zhǎng)了，超過(guò)了對(duì)應(yīng)題目的時(shí)間限制。").
### 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. 由于頭節(jié)點(diǎn)不定，我們使用`dummy`節(jié)點(diǎn)。
1. 使用`last`表示每次歸并后的新鏈表末尾節(jié)點(diǎn)。
1. `count`用于累計(jì)鏈表表頭節(jié)點(diǎn)為`NULL`的個(gè)數(shù)，若與 vector 大小相同則代表所有節(jié)點(diǎn)均已遍歷完。
1. `tempVal`用于保存每次比較 vector 中各鏈表表頭節(jié)點(diǎn)中的最小值，`index`保存本輪選擇歸并過(guò)程中最小值對(duì)應(yīng)的鏈表索引，用于循環(huán)結(jié)束前遞推該鏈表表頭節(jié)點(diǎn)。
### 復(fù)雜度分析
由于每次`for`循環(huán)只能選擇出一個(gè)最小值，總的時(shí)間復(fù)雜度最壞情況下為 O(k?∑i=1kli)O(k \cdot \sum ^{k}_{i=1}l_i)O(k?∑i=1kli). 空間復(fù)雜度近似為 O(1)O(1)O(1).
### 題解2 - 迭代調(diào)用`Merge Two Sorted Lists`([TLE](# "Time Limit Exceeded 的簡(jiǎn)稱。你的程序在 OJ 上的運(yùn)行時(shí)間太長(zhǎng)了，超過(guò)了對(duì)應(yīng)題目的時(shí)間限制。"))
鑒于題解1時(shí)間復(fù)雜度較高，題解2中我們可以反復(fù)利用時(shí)間復(fù)雜度相對(duì)較低的 [Merge Two Sorted Lists | Data Structure and Algorithm](http://algorithm.yuanbin.me/zh-cn/linked_list/merge_two_sorted_lists.html). 即先合并鏈表1和2，接著將合并后的新鏈表再與鏈表3合并，如此反復(fù)直至 vector 內(nèi)所有鏈表均已完全合并[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;
}
};
~~~
### 源碼分析
實(shí)現(xiàn)合并兩個(gè)鏈表的子方法后就沒(méi)啥難度了，`mergeKLists`中左半部分鏈表初始化為`lists[0]`, `for`循環(huán)后迭代歸并`head`和`lists[i]`.
### 復(fù)雜度分析
合并兩個(gè)鏈表時(shí)最差時(shí)間復(fù)雜度為 O(l1+l2)O(l_1+l_2)O(l1+l2), 那么在以上的實(shí)現(xiàn)中總的時(shí)間復(fù)雜度可近似認(rèn)為是 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復(fù)雜度是要小一點(diǎn)，但量級(jí)上仍然差不太多。實(shí)際運(yùn)行時(shí)間也證明了這一點(diǎn)，題解2的運(yùn)行時(shí)間差不多時(shí)題解1的一半。那么還有沒(méi)有進(jìn)一步降低時(shí)間復(fù)雜度的可能呢？當(dāng)然是有的，且看下題分解...
### 題解3 - 二分調(diào)用`Merge Two Sorted Lists`
題解2中`merge2Lists`優(yōu)化空間不大，那咱們就來(lái)看看`mergeKLists`中的`for`循環(huán)，仔細(xì)觀察可得知第`i`個(gè)鏈表 lil_ili 被遍歷了 k?ik-ik?i 次，如果我們使用二分法對(duì)其進(jìn)行歸并呢？從中間索引處進(jìn)行二分歸并后，每個(gè)鏈表參與合并的次數(shù)變?yōu)?logk\log klogk, 故總的時(shí)間復(fù)雜度可降至 logk?∑i=1kli\log k \cdot \sum _{i=1} ^{k} l_ilogk?∑i=1kli. 優(yōu)化幅度較大。
### 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`. 雖然第二種邊界條件可以略去，但是加上會(huì)節(jié)省遞歸調(diào)用的?？臻g。
1. 使用分治思想理解`helper`, `left`和`right`的邊界處理建議先分析幾個(gè)簡(jiǎn)單例子，做到不重不漏。
1. 注意`merge2Lists`中傳入的參數(shù)，為`lists[start]`而不是`start`...
在`mergeKLists`中調(diào)用`helper`時(shí)傳入的`end`參數(shù)為`lists.size() - 1`，而不是`lists.size()`.
### 復(fù)雜度分析
題解中已分析過(guò)，最壞的時(shí)間復(fù)雜度為 logk?∑i=1kli\log k \cdot \sum _{i=1} ^{k} l_ilogk?∑i=1kli, 空間復(fù)雜度近似為 O(1)O(1)O(1).
優(yōu)化后的運(yùn)行時(shí)間顯著減少！由題解2中的500+ms 減至40ms 以內(nèi)。
### Reference
- soulmachine
> .
[soulmachine的LeetCode 題解](#)[ ?](# "Jump back to footnote [soulmachine] in the text.")
- Preface
- Part I - Basics
- Basics Data Structure
- String
- Linked List
- Binary Tree
- Huffman Compression
- Queue
- Heap
- Stack
- Set
- Map
- Graph
- Basics Sorting
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort
- Bucket Sort
- Counting Sort
- Radix Sort
- Basics Algorithm
- Divide and Conquer
- Binary Search
- Math
- Greatest Common Divisor
- Prime
- Knapsack
- Probability
- Shuffle
- Basics Misc
- Bit Manipulation
- Part II - Coding
- String
- strStr
- Two Strings Are Anagrams
- Compare Strings
- Anagrams
- Longest Common Substring
- Rotate String
- Reverse Words in a String
- Valid Palindrome
- Longest Palindromic Substring
- Space Replacement
- Wildcard Matching
- Length of Last Word
- Count and Say
- Integer Array
- Remove Element
- Zero Sum Subarray
- Subarray Sum K
- Subarray Sum Closest
- Recover Rotated Sorted Array
- Product of Array Exclude Itself
- Partition Array
- First Missing Positive
- 2 Sum
- 3 Sum
- 3 Sum Closest
- Remove Duplicates from Sorted Array
- Remove Duplicates from Sorted Array II
- Merge Sorted Array
- Merge Sorted Array II
- Median
- Partition Array by Odd and Even
- Kth Largest Element
- Binary Search
- Binary Search
- Search Insert Position
- Search for a Range
- First Bad Version
- Search a 2D Matrix
- Search a 2D Matrix II
- Find Peak Element
- Search in Rotated Sorted Array
- Search in Rotated Sorted Array II
- Find Minimum in Rotated Sorted Array
- Find Minimum in Rotated Sorted Array II
- Median of two Sorted Arrays
- Sqrt x
- Wood Cut
- Math and Bit Manipulation
- Single Number
- Single Number II
- Single Number III
- O1 Check Power of 2
- Convert Integer A to Integer B
- Factorial Trailing Zeroes
- Unique Binary Search Trees
- Update Bits
- Fast Power
- Hash Function
- Count 1 in Binary
- Fibonacci
- A plus B Problem
- Print Numbers by Recursion
- Majority Number
- Majority Number II
- Majority Number III
- Digit Counts
- Ugly Number
- Plus One
- Linked List
- Remove Duplicates from Sorted List
- Remove Duplicates from Sorted List II
- Remove Duplicates from Unsorted List
- Partition List
- Two Lists Sum
- Two Lists Sum Advanced
- Remove Nth Node From End of List
- Linked List Cycle
- Linked List Cycle II
- Reverse Linked List
- Reverse Linked List II
- Merge Two Sorted Lists
- Merge k Sorted Lists
- Reorder List
- Copy List with Random Pointer
- Sort List
- Insertion Sort List
- Check if a singly linked list is palindrome
- Delete Node in the Middle of Singly Linked List
- Rotate List
- Swap Nodes in Pairs
- Remove Linked List Elements
- Binary Tree
- Binary Tree Preorder Traversal
- Binary Tree Inorder Traversal
- Binary Tree Postorder Traversal
- Binary Tree Level Order Traversal
- Binary Tree Level Order Traversal II
- Maximum Depth of Binary Tree
- Balanced Binary Tree
- Binary Tree Maximum Path Sum
- Lowest Common Ancestor
- Invert Binary Tree
- Diameter of a Binary Tree
- Construct Binary Tree from Preorder and Inorder Traversal
- Construct Binary Tree from Inorder and Postorder Traversal
- Subtree
- Binary Tree Zigzag Level Order Traversal
- Binary Tree Serialization
- Binary Search Tree
- Insert Node in a Binary Search Tree
- Validate Binary Search Tree
- Search Range in Binary Search Tree
- Convert Sorted Array to Binary Search Tree
- Convert Sorted List to Binary Search Tree
- Binary Search Tree Iterator
- Exhaustive Search
- Subsets
- Unique Subsets
- Permutations
- Unique Permutations
- Next Permutation
- Previous Permuation
- Unique Binary Search Trees II
- Permutation Index
- Permutation Index II
- Permutation Sequence
- Palindrome Partitioning
- Combinations
- Combination Sum
- Combination Sum II
- Minimum Depth of Binary Tree
- Word Search
- Dynamic Programming
- Triangle
- Backpack
- Backpack II
- Minimum Path Sum
- Unique Paths
- Unique Paths II
- Climbing Stairs
- Jump Game
- Word Break
- Longest Increasing Subsequence
- Palindrome Partitioning II
- Longest Common Subsequence
- Edit Distance
- Jump Game II
- Best Time to Buy and Sell Stock
- Best Time to Buy and Sell Stock II
- Best Time to Buy and Sell Stock III
- Best Time to Buy and Sell Stock IV
- Distinct Subsequences
- Interleaving String
- Maximum Subarray
- Maximum Subarray II
- Longest Increasing Continuous subsequence
- Longest Increasing Continuous subsequence II
- Graph
- Find the Connected Component in the Undirected Graph
- Route Between Two Nodes in Graph
- Topological Sorting
- Word Ladder
- Bipartial Graph Part I
- Data Structure
- Implement Queue by Two Stacks
- Min Stack
- Sliding Window Maximum
- Longest Words
- Heapify
- Problem Misc
- Nuts and Bolts Problem
- String to Integer
- Insert Interval
- Merge Intervals
- Minimum Subarray
- Matrix Zigzag Traversal
- Valid Sudoku
- Add Binary
- Reverse Integer
- Gray Code
- Find the Missing Number
- Minimum Window Substring
- Continuous Subarray Sum
- Continuous Subarray Sum II
- Longest Consecutive Sequence
- Part III - Contest
- Google APAC
- APAC 2015 Round B
- Problem A. Password Attacker
- Microsoft
- Microsoft 2015 April
- Problem A. Magic Box
- Problem B. Professor Q's Software
- Problem C. Islands Travel
- Problem D. Recruitment
- Microsoft 2015 April 2
- Problem A. Lucky Substrings
- Problem B. Numeric Keypad
- Problem C. Spring Outing
- Microsoft 2015 September 2
- Problem A. Farthest Point
- Appendix I Interview and Resume
- Interview
- Resume