[LeetCode]23.Merge k Sorted Lists

【题目】

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

【分析】

无

【代码】

/*********************************
*   日期：2015-01-06
*   作者：SJF0115
*   题目: 23.Merge k Sorted Lists
*   来源：https://oj.leetcode.com/problems/merge-k-sorted-lists/
*   结果：Time Limit Exceeded
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <vector>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL){}
};

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *head = NULL;
        if(lists.size() == 0){
            return head;
        }//if
        for(int i = 0;i < lists.size();i++){
            head = mergeTwoLists(head,lists[i]);
        }//for
        return head;
    }
private:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;

        if(l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l2->next, l1);
            return l2;
        }
    }
};
// 创建链表
ListNode* CreateList(int A[],int n){
    ListNode *head = NULL;
    if(n <= 0){
        return head;
    }//if
    head = new ListNode(A[0]);
    ListNode *p1 = head;
    for(int i = 1;i < n;i++){
        ListNode *node = new ListNode(A[i]);
        p1->next = node;
        p1 = node;
    }//for
    return head;
}

int main() {
    Solution solution;
    vector<ListNode*> vecs;
    int A[] = {1,2,4,7,9};
    int B[] = {3,5,8,10,11,12};
    int C[] = {6,10,13};
    int D[] = {15,16,17,23};

    ListNode* head1 = CreateList(A,5);
    ListNode* head2 = CreateList(B,6);
    ListNode* head3 = CreateList(C,3);
    ListNode* head4 = CreateList(D,4);

    vecs.push_back(head1);
    vecs.push_back(head2);
    vecs.push_back(head3);
    vecs.push_back(head4);

    ListNode *head = solution.mergeKLists(vecs);
    // 输出
    ListNode *p = head;
    while(p){
        cout<<p->val<<" ";
        p = p->next;
    }//while
    cout<<endl;
}

这种方法超时。。。。。。。

【分析二】

采用最小优先级队列。

第一步：把非空的链表装进最小优先级队列中。

第二步：遍历最小优先级队列，直到最小优先级队列空为止。每次遍历，都能从最小优先级队列中取出具有当前最小的元素的链表。

如果除最小元素之外，链表不空，重新装进最小优先级队列中。

【代码二】

/*********************************
*   日期：2015-01-06
*   作者：SJF0115
*   题目: 23.Merge k Sorted Lists
*   来源：https://oj.leetcode.com/problems/merge-k-sorted-lists/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <queue>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL){}
};

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *head = new ListNode(-1);
        ListNode *p = head;
        // 最小优先级队列
        priority_queue<ListNode*,vector<ListNode*>,cmp> Heap;
        // 链表加入优先级队列
        for(int i = 0;i < lists.size();i++){
            if(lists[i] != NULL){
                Heap.push(lists[i]);
            }//if
        }//for
        // merge
        while(!Heap.empty()){
            // 最小的
            ListNode *list = Heap.top();
            Heap.pop();
            p->next = list;
            p = list;
            if(list->next != NULL){
                Heap.push(list->next);
            }//if
        }//while
        return head->next;
    }
private:
    // 用于最小优先级队列
    struct cmp {
        bool operator()(ListNode* node1, ListNode* node2) {
            return node1->val > node2->val;
        }//bool
    };
};
// 创建链表
ListNode* CreateList(int A[],int n){
    ListNode *head = NULL;
    if(n <= 0){
        return head;
    }//if
    head = new ListNode(A[0]);
    ListNode *p1 = head;
    for(int i = 1;i < n;i++){
        ListNode *node = new ListNode(A[i]);
        p1->next = node;
        p1 = node;
    }//for
    return head;
}

int main() {
    Solution solution;
    vector<ListNode*> vecs;
    int A[] = {1,2,4,7,9};
    int B[] = {3,5,8,10,11,12};
    int C[] = {6,10,13};
    int D[] = {15,16,17,23};

    ListNode* head1 = CreateList(A,5);
    ListNode* head2 = CreateList(B,6);
    ListNode* head3 = CreateList(C,3);
    ListNode* head4 = CreateList(D,4);

    vecs.push_back(head1);
    vecs.push_back(head2);
    vecs.push_back(head3);
    vecs.push_back(head4);

    ListNode *head = solution.mergeKLists(vecs);
    // 输出
    ListNode *p = head;
    while(p){
        cout<<p->val<<" ";
        p = p->next;
    }//while
    cout<<endl;
}

【分析三】

I think my code's complexity is also O(nlogk) and not using heap or priority queue, n means the total elements and k means the size of list.

The mergeTwoLists functiony in my code comes from the problem Merge Two Sorted Listswhose complexity obviously
is O(n), n is the sum of length of l1 and l2.

To put it simpler, assume the k is 2^x, So the progress of combination is like a full binary tree, from bottom to top. So on every level of tree, the combination complexity is n, beacause every level have all n numbers without repetition. The level of tree
is x, ie logk. So the complexity isO(nlogk).

for example, 8 ListNode, and the length of every ListNode is x1, x2, x3, x4, x5, x6, x7, x8, total is n.

on level 3: x1+x2, x3+x4, x5+x6, x7+x8 sum: n

on level 2: x1+x2+x3+x4, x5+x6+x7+x8 sum: n

on level 1: x1+x2+x3+x4+x5+x6+x7+x8 sum: n

total 3n, nlog8

【代码三】

/*********************************
*   日期：2015-01-07
*   作者：SJF0115
*   题目: 23.Merge k Sorted Lists
*   来源：https://oj.leetcode.com/problems/merge-k-sorted-lists/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <limits.h>
#include <queue>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL){}
};

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int count = lists.size();
        if(count == 0){
            return NULL;
        }//if
        if(count == 1){
            return lists[0];
        }//if
        // 链表集合分成两份
        vector<ListNode *> leftLists;
        for(int i = 0;i < count/2;i++){
            leftLists.push_back(lists.back());
            lists.pop_back();
        }//for
        // 分治
        return mergeTwoLists(mergeKLists(leftLists),mergeKLists(lists));
    }
private:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *head = new ListNode(-1);
        for(ListNode *p = head;l1 != NULL || l2 != NULL;p = p->next){
            int val1 = (l1 == NULL) ? INT_MAX : l1->val;
            int val2 = (l2 == NULL) ? INT_MAX : l2->val;
            if(val1 <= val2){
                p->next = l1;
                l1 = l1->next;
            }//if
            else{
                p->next = l2;
                l2 = l2->next;
            }//else
        }//for
        return head->next;
    }
};
// 创建链表
ListNode* CreateList(int A[],int n){
    ListNode *head = NULL;
    if(n <= 0){
        return head;
    }//if
    head = new ListNode(A[0]);
    ListNode *p1 = head;
    for(int i = 1;i < n;i++){
        ListNode *node = new ListNode(A[i]);
        p1->next = node;
        p1 = node;
    }//for
    return head;
}

int main() {
    Solution solution;
    vector<ListNode*> vecs;
    int A[] = {1,2,4,7,9};
    int B[] = {3,5,8,10,11,12};
    int C[] = {6,10,13};
    int D[] = {15,16,17,23};

    ListNode* head1 = CreateList(A,5);
    ListNode* head2 = CreateList(B,6);
    ListNode* head3 = CreateList(C,3);
    ListNode* head4 = CreateList(D,4);

    vecs.push_back(head1);
    vecs.push_back(head2);
    vecs.push_back(head3);
    vecs.push_back(head4);

    ListNode *head = solution.mergeKLists(vecs);
    // 输出
    ListNode *p = head;
    while(p){
        cout<<p->val<<" ";
        p = p->next;
    }//while
    cout<<endl;
}
时间： 2024-04-27 11:27:22

[LeetCode]23.Merge k Sorted Lists的相关文章

LeetCode 23 Merge k Sorted Lists（合并K个已排序链表）

翻译 合并K个已排序的链表,并且将其排序并返回. 分析和描述其复杂性. 原文 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. 代码 我们采用分治的方法来解决这个问题,其有K个链表,不断将其划分(partition),再将其归并(merge). 划分的部分并不难,将其不断分成两部分,但是需要注意的是可能出现start和end相等的情况,这时候就直接r

[LeetCode]21.Merge Two Sorted Lists

[题目] Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. [分析] 无 [代码] /********************************* * 日期:2015-01-06 * 作者:SJF0115 * 题目: 21.Merge Two Sorted L

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. 思路:开始做过两两合并的链表,此时做k路合并,即将k个链表进行合并,可以先将这k个链表进行两两合并,知道合并为一个链表.直接调用前面写过的两两合并的例子.   C++代码实现: #include<iostream> #include<new> #include<vector>

LeetCode 21 Merge Two Sorted Lists（合并两个已排序的数组）

翻译 合并两个排好序的链表,并返回这个新链表. 新链表应该由这两个链表的头部拼接而成. 原文 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. 代码 /** * Definition for singly-linked list. * struct ListNode

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. C++代码如下: #include<iostream> #include<new> using namespace std; //Definition for singly-linked list. s

Java&amp;amp;quot;merge two sorted lists into a new sorted one&amp;amp;quot;

问题描述 seekhelp!howcanIcreate"publicstaticSortedListmergeList(SortedListlist1,SortedListlist2)"methodThismethodcanmergetwosortedlistsintoanewsortedone,andreturnareferenceofthenewlist.Theprogramshouldgothrougheachlinkiteminbothlists,anddirectlylink

[LeetCode] Accounts Merge 账户合并

Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account. Now, we would like to merge these accounts. Two accoun

c++-leetcode Median of Two Sorted Arrays

问题描述 leetcode Median of Two Sorted Arrays class Solution { public: double findMedianSortedArrays(vector& nums1, vector& nums2) { if(nums1.size()==0){ if(nums2.size()%2==0)return ((double)nums2[nums2.size()/2]+nums2[nums2.size()/2-1])/2.0; else ret

[LeetCode] Partition to K Equal Sum Subsets 分割K个等和的子集

Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into knon-empty subsets whose sums are all equal. Example 1: Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4 Output: True Explanation: It's possible