首页 > 代码库 > Merge k Sorted Lists

Merge k Sorted Lists

2024-07-03 22:37:57   226人阅读

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

思路：合并k个有序链表为一个有序链表。我们可以用先合并两个链表的方法，然后逐个遍历链表数组，与上一个合并结束的链表进行合并，这样最后就可以得到一个有序链表了。这样做的时间复杂度在O(n*k),有点高了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeList(ListNode *pHead1,ListNode *pHead2)
    {
        if(pHead1==NULL)
            return pHead2;
        else if(pHead2==NULL)
            return pHead1;
        ListNode *pMergeHead=NULL;
        if(pHead1->val<pHead2->val)
        {
            pMergeHead=pHead1;
            pMergeHead->next=mergeList(pHead1->next,pHead2);
        }
        else
        {
            pMergeHead=pHead2;
            pMergeHead->next=mergeList(pHead1,pHead2->next);
        }
        return pMergeHead;
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int n=lists.size();
        if(n<=0)
            return NULL;
        ListNode *head=lists[0];
        for(int i=1;i<n;i++)
        {
            head=mergeList(head,lists[i]);
        }
        return head;
    }
};

思路二：借用网上大神的做法，时间复杂度在O(nlogk).使用堆的做法，是用C++的STL的优先队列，解决此问题。没想到STL的优先队列竟然可以如此用，太强大了，学习了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 struct cmp
 {
     bool operator()(ListNode *pNode1,ListNode *pNode2)
     {
         return pNode1->val > pNode2->val;
     }
 };
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode *,vector<ListNode *>,cmp> queue;
        for(int i=0;i<lists.size();i++)
        {
            if(lists[i]!=NULL)
            {
                queue.push(lists[i]);
            }
        }
        ListNode *head=NULL;
        ListNode *pPre=NULL;
        ListNode *pList;
        while(!queue.empty())
        {
            pList=queue.top();
            queue.pop();
            if(pPre==NULL)
                head=pList;
            else
                pPre->next=pList;
            pPre=pList;
            if(pList->next!=NULL)
                queue.push(pList->next);
        }
        return head;
    }
};

 


联系
我们