合并K个排序链表

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

解题思路

python的优势，heapq堆排序
应该是第三次用到heapq了吧，希望下次再使用的时候，心里有数了。其实只要记得，该方法就是可以自动的将输入的值，进行堆排序（小顶堆）。意味着，每次输出结果，使用heapq.heappop()
就可以输出最小值。内部代码自动维护堆排序。很方便

代码

Code

import heapq
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists:
            return 
        h = []
        for l in lists:
            p = l

            while p:
                heapq.heappush(h, p.val)
                p = p.next 
        if not h:
            return
        head = ListNode(heapq.heappop(h))
        p = head
        while h:
            p.next = ListNode(heapq.heappop(h))
            p = p.next 
        return head

解题思路

链表两两合并

代码

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists:
            return 
        l1 = None
        st = 0
        for i, l in enumerate(lists):
            if not l:
                continue
            l1 = l 
            st = i
            break

        def mergelist(l1,l2):
            if l1.val < l2.val:
                head = l1
                l1 = l1.next
            else:
                head = l2
                l2 =l2.next
            p = head
            while l1 and l2:
                if l1.val > l2.val:
                    p.next = l2 
                    p =p.next 
                    l2 = l2.next
                else:
                    p.next = l1 
                    p = p.next 
                    l1 = l1.next 
            if l1:
                p.next = l1
            else:
                p.next = l2
            return head
        if not l1:
            return 
        for i in range(st+1, len(lists)):
            l2 = lists[i]
            if not l2:
                continue
            l1 = mergelist(l1,l2)  
        return l1