题解 | #合并k个已排序的链表#

所有调试代码

struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};

// 合并两个链表
ListNode* mergeTwoLists(ListNode* head1, ListNode* head2) {
  if (head1 == nullptr && head2 == nullptr) return nullptr;
  if (head2 == nullptr) return head1;
  if (head1 == nullptr) return head2;
  ListNode* dummy = new ListNode(0);
  ListNode* p = dummy;
  while (head1 && head2) {
    if (head1->val < head2->val) {
      p->next = head1;
      head1 = head1->next;
    } else {
      p->next = head2;
      head2 = head2->next;
    }
    p = p->next;
  }
  if (head1) p->next = head1;
  if (head2) p->next = head2;
  return dummy->next;
}

ListNode* merge(vector<ListNode *> &lists, int left, int right) {
  if (left == right) return lists[left];
  if (left > right) return nullptr;
  int mid = left + (right - left) / 2;
  return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right));
}

ListNode *mergeKLists(vector<ListNode *> &lists) {
  int n = lists.size();
  if (n == 0) return nullptr;
  if (n == 1) return lists.front();
  return merge(lists, 0, n-1);
}

ListNode* createList(const vector<int>& vec) {
  ListNode* dummy = new ListNode(0);
  ListNode* p = dummy;
  for (auto& v : vec) {
    auto node = new ListNode(v);
    p->next = node;
    p = p->next;
  }
  return dummy->next;
}

vector<ListNode*> createLists(const vector<vector<int>>& vec) {
  vector<ListNode*> ans;
  for (const auto& v : vec) {
    ans.push_back(createList(v));
  }
  return ans;
}

int main() {
  vector<vector<int>> vec = { {-10,-10,-8,-4,-4,-2,0,3},{-8,-5,-3,-2,1},
                              {-9,-9,0,1},{-10,-8,-7,-4,-2,-1,-1,1,3},
                              {-7,-5,-2,0,0,3,3},{-6,-5,-5,-3,-2,-1,0,1,4} };
  auto lists = createLists(vec);
  auto head = mergeKLists(lists);

  return 0;
}