#LeetCode：23. Merge k Sorted Lists

將題目想像成是在做 Merge Sort 的最後一步合併兩個排序好的陣列回來，故可將這 k 個排序好的陣列利用Divide & Conquer的方式兩個兩個合併回來，至於合併兩個排序好的陣列可見#LeetCode：21. Merge Two Sorted Lists
。

C++(16ms)

/*******************************************************/
/* LeetCode 23. Merge k Sorted Lists                   */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2018/10/17                                 */
/*******************************************************/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode* mergeLists(vector<ListNode*>& lists, int startIndex, int endIndex){
    int size = endIndex - startIndex;
    if(size == 0) return NULL;
    if(size == 1) return lists[startIndex];

    ListNode *leftSide = mergeLists(lists, startIndex, startIndex + size / 2);
    ListNode *rightSide = mergeLists(lists, startIndex + size / 2, endIndex);
    ListNode headNode(-1);
    ListNode *mergedList = &headNode;
    ListNode *currentNode = mergedList;
    while(leftSide != NULL && rightSide != NULL){
      if(leftSide->val < rightSide->val){
        currentNode->next = leftSide;
        leftSide = leftSide->next;
      }
      else{
        currentNode->next = rightSide;
        rightSide = rightSide->next;
      }

      currentNode = currentNode->next;
    }

    currentNode->next = (leftSide != NULL)? leftSide : rightSide;
    return mergedList->next;
  }

  ListNode* mergeKLists(vector<ListNode*>& lists) {
    return mergeLists(lists, 0, lists.size());
  }
};