LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 不断划分，最后两两合并即可

class Solution {
 public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    return mergeKLists(lists, 0, size(lists));
  }

  ListNode* mergeKLists(vector<ListNode*>& lists, int l, int r) {
    if (l == r) {
      return nullptr;
    }
    if (l == r - 1) {
      return lists[l];
    }
    if (l == r - 2) {
      return mergeTwoLists(lists[l], lists[l + 1]);
    }
    int m = l + (r - l) / 2;
    ListNode* l1 = mergeKLists(lists, l, m);
    ListNode* l2 = mergeKLists(lists, m, r);
    return mergeTwoLists(l1, l2);
  }

  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) {
      return l2;
    }
    if (!l2) {
      return l1;
    }
    if (l1->val < l2->val) {
      l1->next = mergeTwoLists(l1->next, l2);
      return l1;
    }
    l2->next = mergeTwoLists(l2->next, l1);
    return l2;
  }
};

• 其过程为

l = [a, b, c, d, e, f]  // 每个元素是一个有序链表

l1 = [a, b, c]
l2 = [d, e, f]

l1.1 = a
l1.2 = [b, c]
l2.1 = d
l2.2 = [e, f]

// 实际合并过程如下
l1.1 = a
l1.2.1 = b
l1.2.2 = c
l2.1 = d
l2.2.1 = e
l2.2.2 = f

l1.1 = a
l1.2 = [b, c]  // 重新合并后的 bc
l2.1 = d
l2.2 = [e, f]

l1 = [a, b, c]
l2 = [d, e, f]

l = [a, b, c, d, e, f]