首页 > 其他 > 详细

[LeetCode] Merge k Sorted Lists

时间:2015-07-06 01:24:39      阅读:283      评论:0      收藏:0      [点我收藏+]

Well, the idea of this problem is actually very sample --- keep merging the unmerged lists in lists until there is exactly one list remained. However, do not merge lists[0] with lists[1], lists[2], ..., lists[n - 1] sequentially since that will cause TLE. You may merge the first two lists and then push it back to lists and erase the first two to avoid repeated merging, or use some variables to control the merging process, as the following code.

 1 class Solution {
 2 public:
 3     ListNode* mergeKLists(vector<ListNode*>& lists) {
 4         if (lists.empty()) return NULL;
 5         int n = lists.size();
 6         while (n > 1) {
 7             for (int i = 0; i < n / 2; i++)
 8                 lists[i] = mergeLists(lists[i], lists[n - 1 - i]);
 9             n = (n + 1) / 2;
10         }
11         return lists[0];
12     }
13 private:
14     ListNode* mergeLists(ListNode* head1, ListNode* head2) {
15         ListNode* new_head = new ListNode(0);
16         ListNode* run = new_head;
17         ListNode* run1 = head1;
18         ListNode* run2 = head2;
19         while (run1 && run2) {
20             if (run1 -> val <= run2 -> val) {
21                 run -> next = run1;
22                 run1 = run1 -> next;
23             }
24             else {
25                 run -> next = run2;
26                 run2 = run2 -> next;
27             }
28             run = run -> next;
29         }
30         run -> next = run1 ? run1 : run2;
31         return new_head -> next;
32     }
33 };

 

[LeetCode] Merge k Sorted Lists

原文:http://www.cnblogs.com/jcliBlogger/p/4623367.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!