Skip to content

23. merge k sorted lists

难度: Hard

刷题内容

原题连接

  • https://leetcode.com/problems/merge-k-sorted-lists/

内容描述

Merge k sorted 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

解题方案

思路1 **- 时间复杂度: O(Nlg(K))*- 空间复杂度: O(K)***

这里运用最小堆,先去每个链表的第一个元素构建最小堆,由于链表都是已排序的,因此,每次堆的顶部都是最小的元素,这里用优先队列实现最小堆。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    struct cmp
    {
        bool operator()(ListNode* a, ListNode* b) const
        {
            return a ->val > b ->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {  
        priority_queue<ListNode*,vector<ListNode*>,cmp> pq;
        ListNode* ret = nullptr;
        ListNode* current = nullptr;
        for(int i = 0;i < lists.size();++i)
            if(lists[i])
                pq.push(lists[i]);
        while(pq.size())
        {
            ListNode* temp = pq.top();
            pq.pop();
            if(!ret)
                ret = temp;
            else
                current ->next = temp;
            current = temp;
            if(temp ->next)
                pq.push(temp ->next);
        }
        return ret;
    }
};

思路2 **- 时间复杂度: O(Nlg(K))*- 空间复杂度: O(1)***

这个思路用分治思想,我们可以通过归并排序解决,首先前面已经做过了两个有序链表的排序,我们可以把链表看做元素,只要对数组 Lists进行归并排序即可。

class Solution {
public:
    ListNode* merge(ListNode* list1, ListNode* list2) {
        ListNode head(0);
        ListNode* tail = &head;
        auto cur1 = list1;
        auto cur2 = list2;
        while (cur1 != nullptr && cur2 != nullptr) {
            if (cur1->val < cur2->val) {
                tail->next = cur1;
                tail = tail->next;
                cur1 = cur1->next;
            } else {
                tail->next = cur2;
                tail = tail->next;
                cur2 = cur2->next;
            }
        }
        auto cur = cur1 == nullptr ? cur2 : cur1;
        while (cur != nullptr) {
            tail->next = cur;
            tail = tail->next;
            cur = cur->next;
        }
        return head.next;
    }
    ListNode* mergeSort(vector<ListNode*>& lists, int start, int end) {
        if (start > end) {
            return nullptr;
        }
        if (start == end) {
            return lists[start];
        }
        int mid = start + (end - start) / 2;
        auto list1 = mergeSort(lists, start, mid);
        auto list2 = mergeSort(lists, mid + 1, end);
        return merge(list1, list2);
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        return mergeSort(lists, 0, n - 1);
    }
};


回到顶部