Title:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
排好序的，然后merge，很容易让人联想到归并排序。可以将k个序列按照二分进行分割，然后当长度为1时返回一个排好序的序列，最后将两个序列merge
class Solution{ public: ListNode* merge(ListNode* list1, ListNode* list2){ ListNode head(0),*tail = &head; while (list1 != NULL && list2 != NULL){ if (list1->val < list2->val){ tail->next = list1; tail = list1; list1 = list1->next; }else{ tail->next = list2; tail = list2; list2 = list2->next; } } if (list1 != NULL){ tail->next = list1; } if (list2 != NULL){ tail->next = list2; } return head.next; } ListNode* divide(int l,int r,vector<ListNode* > &lists){ int m = (l + r) / 2; if (l < r){ return merge(divide(l,m,lists),divide(m+1,r,lists)); }else return lists[l]; } ListNode* mergeKLists(vector<ListNode* > &lists){ int k = lists.size(); if (0 == k) return NULL; return divide(0,k-1,lists); } };
原文：http://www.cnblogs.com/yxzfscg/p/4427559.html