LeetCode HOT100 - 合并 K 个升序链表

熟悉的形式是合并两个链表

那要合并多个的时候想想能不能从这个基础情况推导出去

如果是合并完两个，再接着合并下一个，这样显然有些繁琐

注意到链表合并是和顺序，大小都无关的

也就是说我们只关注数量

那么不妨分治

也就是两两合并

因为顺序无关，所以左右各自合并，然后再左右合并没有问题

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& a) {auto merge = [](ListNode* x, ListNode* y) -> ListNode* {ListNode* res = new ListNode(), *cur;cur = res;while (x && y) {if (x->val < y->val) {cur->next = x;x = x->next;} else {cur->next = y;y = y->next;}cur = cur->next;}cur->next = x ? x : y;return res->next;};auto merge_array = [&](this auto&& self, int l, int r) -> ListNode* {if (l == r) {return a[l];}int m = (l + r) / 2;auto res = merge(self(l, m), self(m + 1, r));return res;};int n = a.size();if (n == 0) {return nullptr;}return merge_array(0, n - 1);}
};