# Merge k Sorted Lists

## 题解1 - 选择归并(TLE)

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

## 题解2 - 迭代调用Merge Two Sorted Lists(TLE)

### 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;
}

for (int i = 1; i != lists.size(); ++i) {
}

}

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;
}
};


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

### 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;
}
};


### 源码分析

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

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