23. 合并K个排序链表

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

解法一:

思路和两个表合并差不多,每次遍历所有链的头(即lists[i]),找最小节点i插入新链,找到的这个i号链头前移一位,直到链头全为空。

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        Head = ListNode(0)  #新链头
        work = Head    #工作节点
        while any(lists):   #若还有链非空
            minVal = sys.maxsize    #最小值
            index = -1     #最小值链下标
            for i in range(len(lists)):     #遍历所有链,找最小的
                if lists[i]:    #只访问非空链
                    if lists[i].val < minVal:   #更新
                        minVal = lists[i].val   
                        index = i
            work.next = lists[index]    #加入新链
            work = work.next
            lists[index] = lists[index].next    #这个链的头后移一位        
        return Head.next

解法二:

soluition第一种的暴力法,真心暴力,直接遍历每条链的每个节点,把所有记录下来。然后排序,根据排序后的序列构建出一条新链来。。。。

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        nodes = []    #记录所有结点值
        head = work = ListNode(0)
        for l in lists:
            while l:
                nodes.append(l.val)
                l = l.next
        nodes.sort()  #排序
        for x in nodes: #创建新链
            work.next = ListNode(x)
            work = work.next
        return head.next

最后更新于