LeetCode--Merge k Sorted Lists--分治策略

Merge k Sorted Lists--分治策略## [更多技术博客 http://vilins.top/](http://vilins.top/)题目Mergeksorted linked lists and return it as one sorted list. Analyze and describe its complexity.ExampleInput: [ 1-4-5, 1-3-4, 2-6 ] Output: 1-1-2-3-4-4-5-6分析这题是分治策略的很好的应用这里两次运用分治策略的思想先是在把多条链的合并问题转化为两两链的合并问题然后再将分治策略运用到具体的合并过程当中比较开头大小小的链的下一个与另一条链做合并一直递归下去。源码/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeKLists(vectorListNode* lists) { if(lists.size() 0) { return NULL; } //every two merge while(lists.size() 1) { ListNode *temp merge(lists[0], lists[1]); lists.push_back(temp); lists.erase(lists.begin()); lists.erase(lists.begin()); } return lists[0]; } ListNode* merge(ListNode *l1, ListNode *l2) { if(l1 NULL) { return l2; } if(l2 NULL) { return l1; } if(l1-val l2-val) { l1-next merge(l1-next, l2); return l1; } else { l2-next merge(l2-next, l1); return l2; } } };## [更多技术博客 http://vilins.top/](http://vilins.top/)