【问题描述】

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. 问题来源：Merge k Sorted Lists

【解题分析】

将k个有序的数组合并成一个有序的数组，将其分而治之，每次只比较两个数组，简易图为： 如此，我们只需重复将两个数组合并为一个数组。 假设有两个数组A1和A2，比较两个数组的元素A1[i]和A2[j]，将较小的元素放入新数组，如果A1[i]小，则i++；如果A2[j]小，则j++，再接着比较A1[i]和A2[j]，直到一个数组全部进行了比较。

【源代码】

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode* result = NULL; int i = 0; while (i < lists.size()) { MergeTwoLists(result,lists[i]); i++; } return result; } private: void MergeTwoLists(ListNode* &l1, ListNode* l2) { ListNode* newlist = new ListNode(0); ListNode* phead = newlist; while (l1 != NULL && l2 != NULL) { if (l1->val < l2->val) { newlist->next = l1; newlist = newlist->next; l1 = l1->next; } else { newlist->next = l2; newlist = newlist->next; l2 = l2->next; } } if (l1 != NULL) { newlist->next = l1; } if (l2 != NULL) { newlist->next = l2; } l1 = phead->next; } };