526互联

Leetcode 23. 合并 K 个升序链表(分治)

发布时间 2023-03-27 16:36:49作者: 珍珠鸟

题目链接在这里：合并K个升序链表

对于多个升序链表的合并，如果用C++写的话可以使用优先队列，队列里面存放的都是每一个链表的头结点。 也可以使用分治的方法来做，每次将链表两两合并，这样节约了时间。 这道题巩固了python中递归的应用。

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


class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists:
            return []
        n = len(lists)
        return self.merge(lists,0,n-1)

    def merge(self, lists, low, high):
        if low == high:
            return lists[low]
        mid = (low+high) //2
        l = self.merge(lists, low, mid)
        h = self.merge(lists, mid+1, high)
        return self.mergetwo(l,h)
    def mergetwo(self,list1,list2):
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val<list2.val:
            list1.next = self.mergetwo(list1.next,list2)
            return list1
        else:
            list2.next = self.mergetwo(list1,list2.next)
            return list2