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.

Example

Input: [ 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(vector<ListNode*>& 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/)