Jianbo Dai's

mq045.合并K个排序链表

 
  • Jan 08, 2021

题目链接

这个题目上来先尝试了一下顺序合并，就是依次把链表合并但是这样的时间复杂度很高为O（KN^2），其中K是链表的平均长度，N为链表总数。其空间复杂度为O（1）。

所以只能换成分治合并算法，这个算法的时间复杂度是O（NKxlogK），空间复杂度是O（logN）。

然后，还有一种方法是用堆来做，由于需要得到一个升序列表，说明我们需要做一个小顶堆。该算法如3所示，时间复杂度为O(KNxlogK)，空间复杂度为O（NK）。不过这应该不是最正宗的那种利用优先队列的，讲道理应该用优先队列维护一个最长为N的列表，先将所有链表的头部节点加入之后然后依此pop和push相应的链表的下一个节点。

python:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists1(self, lists: List[ListNode]) -> ListNode:
        if not lists:
            return 
        ans = lists[0]
        for ele in lists[1:]:
            ans = self.mergeTwo(ans, ele)
        return ans

    def mergeTwo(self, lst1, lst2):
        prev = prehead = ListNode(-1)
        while lst1 and lst2:
            if lst1.val <= lst2.val:
                prev.next = lst1
                lst1 = lst1.next
            else:
                prev.next = lst2
                lst2 = lst2.next
            prev = prev.next
        
        prev.next = lst1 if lst1 is not None else lst2
        return prehead.next

    def mergeKLists2(self, lists: List[ListNode]) -> ListNode:
        return self.merge(lists, 0, len(lists)-1)

    def merge(self, lists, start, end):
        if start > end:
            return 
        if start == end:
            return lists[start]
        mid = (start + end) // 2
        return self.mergeTwo(self.merge(lists, start, mid), self.merge(lists, mid+1, end))

    def mergeKLists3(self, lists: List[ListNode]) -> ListNode:
        if not lists:
            return None
        import heapq
        heap = []
        for node in lists:
            while node:
                heapq.heappush(heap, node.val)
                node = node.next
        dummy = prev = ListNode(None)
        while heap:
            tmp_node = ListNode(heappop(heap))
            prev.next = tmp_node
            prev = tmp_node
        return dummy.next

C++:

class Solution1 {
public:
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if ((!a) || (!b)) return a ? a : b;
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                tail->next = aPtr; aPtr = aPtr->next;
            } else {
                tail->next = bPtr; bPtr = bPtr->next;
            }
            tail = tail->next;
        }
        tail->next = (aPtr ? aPtr : bPtr);
        return head.next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *ans = nullptr;
        for (size_t i = 0; i < lists.size(); ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }
};

class Solution2 {
public:
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if ((!a) || (!b)) return a ? a : b;
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                tail->next = aPtr; aPtr = aPtr->next;
            } else {
                tail->next = bPtr; bPtr = bPtr->next;
            }
            tail = tail->next;
        }
        tail->next = (aPtr ? aPtr : bPtr);
        return head.next;
    }

    ListNode* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};
Search