抱佛脚一时爽，一直抱佛脚一直爽！这篇文章总结常见的归并问题~
参考链接：leetcode 剑指offer

数组中的归并问题

合并有序数组n1 n2到n1（lc88）

• 注意n1的长度一直在变！p2移动后p1也要跟着移动且n1长度要增加！

数组中的逆序对（jz35）

链表中的归并问题

合并两个有序链表（jz16）

• 思路：双指针

合并k个有序链表（lc23）

• 思路：首先把k个链表的首元素都加入最小堆中，它们会自动排好序。然后每次取出最小的那个元素加入最终结果的链表中，然后把取出元素的下一个元素再加入堆中

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) {
      return a->val > b->val;
    };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> q(cmp);
    for (auto head : lists) {
      if (head) q.push(head); // 记住要if(head)！
    }
    ListNode* dummyHead = new ListNode(-1);
    ListNode* cur = dummyHead;
    while (!q.empty()) {
      cur->next = q.top();
      q.pop();
      cur = cur->next;
      if (cur->next) q.push(cur->next);
    }
    return dummyHead->next;
  }

其他问题

合并区间（lc56）

  vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> result;
    if (!intervals.size() || !intervals[0].size()) return result;
    int n = intervals.size();
    sort(intervals.begin(), intervals.end(), [](vector<int>& v1, vector<int>& v2) { return v1[0] < v2[0]; });
    int curLeft = intervals[0][0], curRight = intervals[0][1];
    for (int i = 1; i < n; ++i) {
      vector<int> vec = intervals[i];
      if (vec[0] > curRight) {
        result.push_back({curLeft, curRight});
        curLeft = vec[0];
        curRight = vec[1];
      } else {
        curRight = max(curRight, vec[1]);
      }
    }
    result.push_back({curLeft, curRight});
    return result;
  }