题目：
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
解答：
解答一：在一个循环中，依次将两个链表合并，合并后的结果放到其中一个链表，另一个链表设置为nullptr，代码如下，
ListNode* mergeTwoList(ListNode* l1, ListNode* l2) { if (l1 == nullptr&&l2 == nullptr) return nullptr; if (l1 == nullptr) return l2; if (l2 == nullptr) return l1; ListNode* result = new ListNode(); ListNode* tmp = result; while (l1 != nullptr || l2 != nullptr) { if (l1 == nullptr) { tmp->next = l2; l2 = l2->next; tmp = tmp->next; continue; } if (l2 == nullptr) { tmp->next = l1; l1 = l1->next; tmp = tmp->next; continue; } if (l1->val < l2->val) { tmp->next = l1; l1 = l1->next; tmp = tmp->next; continue; } else { tmp->next = l2; l2 = l2->next; tmp = tmp->next; continue; } } return result->next;; } ListNode* mergeKLists(vector<ListNode*>& lists) { if (lists.size() == 0) return nullptr; else if (lists.size() == 1) return lists.at(0); //从两侧向中间移动，两两合并 int idx1 = 0; int idx2 = lists.size()-1; ListNode* result = nullptr; while (idx1 < idx2) { while (lists.at(idx1) == nullptr && idx1 < idx2)//list中可能有空链表，删除里面的空链表 { idx1++; } while (lists.at(idx2) == nullptr && idx1 < idx2) { idx2--; continue; } if (idx1 == idx2) { if (result == nullptr && lists.at(idx1) != nullptr)//去重后，两个idx可能重复，但是重复的可能是唯一一个不为nullptr的list return lists.at(idx1); break; } //合并两个链表 result = mergeTwoList(lists.at(idx1), lists.at(idx2)); lists.at(idx1) = result; idx2--; } return result; }
提交后通过，但是合并次数为N-1，修改如下
解答二：让vector中的元素两两合并，合并后再递归调用，减少合并次数，分治法
vector<ListNode*> mergeSubStep(vector<ListNode*> lists) { vector<ListNode*> vec; for (auto val : lists) { if (val == nullptr) continue; vec.push_back(val); } if (vec.size() < 2) return vec; vector<ListNode*> tmpVec; int idx1 = 0, idx2 = vec.size() - 1; while (idx1 < idx2) { ListNode* result = mergeTwoList(vec.at(idx1), vec.at(idx2)); tmpVec.push_back(result); idx1++; idx2--; } if (vec.size() % 2 == 1)//奇数个，把中间的添加到vec { tmpVec.push_back(vec.at(idx1)); } return tmpVec; } ListNode* mergeKLists2(vector<ListNode*>& lists) { vector<ListNode*> result = mergeSubStep(lists); if (result.size() == 0) return nullptr; else if (result.size() == 1) return result.at(0); while (true) { result = mergeSubStep(result); if (result.size() < 2) break; } return result.at(0); }
其中，两个链表合并的代码跟解答一中的一样，省略。提交后，相对于解答一，速度提高了很多。
看解答。
一：合并两个链表，解答中的效率较高，代码如下：
ListNode* mergeTwoLists(ListNode *a, ListNode *b) { if ((!a) || (!b)) return a ? a : b; ListNode head, *tail = &head, *aPtr = a, *bPtr = b; while (aPtr && bPtr) { if (aPtr->val < bPtr->val) { tail->next = aPtr; aPtr = aPtr->next; } else { tail->next = bPtr; bPtr = bPtr->next; } tail = tail->next; } tail->next = (aPtr ? aPtr : bPtr); return head.next; }
该函数中，判断是否为nullptr以及比较很少，在两个链表都不为空时取较小值，当其中一个为nullptr后，直接将next指向另一个链表即可。而自己写的合并在一个while中多次判断链表是否为nullptr，效率较低。
二：解答中的分治使用两个index，这样在递归调用时不会产生中间的vector，以节约内存：而且求L+R的平均值时，使用的是右移操作，比除2效率高。
ListNode* merge(vector <ListNode*> &lists, int l, int r) { if (l == r) return lists[l]; if (l > r) return nullptr; int mid = (l + r) >> 1; return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r)); } ListNode* mergeKLists(vector<ListNode*>& lists) { return merge(lists, 0, lists.size() - 1); }