首页 > 其他 > 详细

[LeetCode 题解]: Merge k Sorted Lists

时间:2014-07-29 11:02:16      阅读:362      评论:0      收藏:0      [点我收藏+]

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

题意:对k个有序的链表进行归并排序。并分析其复杂度。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* left, ListNode* right){   //归并操作
        if(left==NULL) return right;
        if(right==NULL) return left;
        ListNode *ans =new ListNode(0);
        if(left->val <= right->val){
            ans=left;
            left = left->next;    
        }else{
            ans=right;
            right=right->next;
        }
        ans->next = merge(left,right);
        return ans;
    }
    ListNode* mergesort(vector<ListNode *> &lists,int left,int right){  //devide && conquer
        if(left>right){
            return NULL;
        }if(left==right){
            return lists[left];
        }else{
            int middle = (left+right)>>1;
            ListNode *lleft = mergesort(lists,left,middle);
            ListNode *lright = mergesort(lists,middle+1,right);
            return merge(lleft,lright);
        }
        
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int left =0,right =lists.size()-1;
        int middle= (left+right)>>1;
        ListNode *lleft = mergesort(lists,left,middle);
        ListNode *lright = mergesort(lists,middle+1,right);
        return merge(lleft,lright);
    }
};

时间复杂度: O(n*logn) 

空间复杂度: O(1)

至于具体的量化分析呢,呵呵。。。数学推导了

转载请注明出处: http://www.cnblogs.com/double-win/ 谢谢!

[LeetCode 题解]: Merge k Sorted Lists,布布扣,bubuko.com

[LeetCode 题解]: Merge k Sorted Lists

原文:http://www.cnblogs.com/double-win/p/3873952.html

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