翻译

合并K个已排序的链表，并且将其排序并返回。
分析和描述其复杂性。

原文

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

代码

我们采用分治的方法来解决这个问题，其有K个链表，不断将其划分（partition），再将其归并（merge）。

划分的部分并不难，将其不断分成两部分，但是需要注意的是可能出现start和end相等的情况，这时候就直接return lists[start]就可以了。

mid = (start + end) / 2
start -- mid                    （1）
mid + 1 -- end                  （2）

上面的（1）和（2）就不断的替换更新，不断作为参数写到partition函数内。

归并的部分也不难，因为在此之前我们已经遇到过，传送门：LeetCode 21 Merge Two Sorted Lists 。

所以结合起来就是下面这样的：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector
   
     &lists) { return partition(lists, 0, lists.size() - 1); } ListNode* partition(vector
    
     & lists, int start, int end) { if(start == end) { return lists[start]; } if(start < end) { int mid = (start + end) / 2; ListNode* l1 = partition(lists, start, mid); ListNode* l2 = partition(lists, mid + 1, end); return mergeTwoLists(l1, l2); } return NULL; } ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l2 == NULL) return l1; if(l1 == NULL) return l2; if(l1->val > l2->val) { ListNode* temp = l2; temp->next = mergeTwoLists(l1, l2->next); return temp; } else { ListNode* temp = l1; temp->next = mergeTwoLists(l1->next, l2); return temp; } } };
    
   

继续学习大神的的解法：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */ 
class Solution {
public:
    ListNode* mergeKLists(vector
   
     &lists) { int size = lists.size(); if(size == 0) return NULL; if(size == 1) return lists[0]; int i = 2, j; while(i / 2 < size) { for(j = 0; j < size; j += i) { ListNode* p = lists[j]; if(j + i / 2 < size) { p = mergeTwoLists(p, lists[j + i / 2]); lists[j] = p; } } i *= 2; } return lists[0]; } ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l2 == NULL) return l1; if(l1 == NULL) return l2; if(l1->val > l2->val) { ListNode* temp = l2; temp->next = mergeTwoLists(l1, l2->next); return temp; } else { ListNode* temp = l1; temp->next = mergeTwoLists(l1->next, l2); return temp; } } };
   

?