leetcode-合并K个排序链表

思路：

1. 首先解决两个链表的合并：

ListNode *mergeTwoList(ListNode *l1, ListNode *l2) {
    ListNode *dummyNode = new ListNode(-1);
    ListNode *curNode = dummyNode;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            curNode->next = l1;
            curNode = l1;
            l1 = l1->next;
        }
        else if (l1->val>l2->val) {
            curNode->next = l2;
            curNode = l2;
            l2 = l2->next;
        }
        else {
            curNode->next = l1;
            curNode = l1;
            l1 = l1->next;
        }
    }
    if (l1) {
        curNode->next = l1;
    }
    if (l2) {
        curNode->next = l2;
    }
    return dummyNode->next;
}

2. 利用分治法解决K个链表的排序：

ListNode *mergeListUsingRecursion(vector<ListNode*> &lists, int begin, int len) {
    if (len == 1) {
        return lists[begin];
    }
    if (len == 2) {
        return mergeTwoList(lists[begin], lists[begin + 1]);
    }
    int dist = (len + 1) / 2;
    ListNode *l1 = mergeListUsingRecursion(lists, begin, dist);
    ListNode *l2 = mergeListUsingRecursion(lists, begin + dist, len - dist);
    return mergeTwoList(l1, l2);
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.size()==0) {
      return NULL;
    }
   return mergeListUsingRecursion(lists,0,lists.size());
}

如果使用非递归版本的分治法，可以这样做：

ListNode *mergeKLists(vector<ListNode *> &lists) {
    if (lists.size() == 0) return NULL;
    int n = lists.size();
    while (n > 1) {
        int k = (n + 1) / 2;
        for (int i = 0; i < n / 2; ++i) {
            lists[i] = mergeTwoLists(lists[i], lists[i + k]);
        }
        n = k;
    }
    return lists[0];
}