题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param lists ListNode类一维数组 # @return ListNode类 # from functools import reduce class Solution: def mergeKLists(self , lists: List[ListNode]) -> ListNode: n = len(lists) if n == 0: return None elif n == 1: return lists[0] def merge(l: ListNode, r: ListNode): if l is None: return r elif r is None: return l ret = ListNode(None) cur = ret while all((l is not None, r is not None)): if l.val < r.val: cur.val = l.val l = l.next else: cur.val = r.val r = r.next cur.next = ListNode(None) cur = cur.next if l is not None: cur.val = l.val cur.next = l.next elif r is not None: cur.val = r.val cur.next = r.next return ret return reduce(merge, lists)
这里的重点在于:如果一个链表节点数为"0"时,实际传入的变量为None,这一点在python的Type hint中并没有指出(应该使用List[Optional[ListNode]])来作为输入。因此,每次reduce时不要忘了判断一下输入的是否为None
以及,由于这个问题错了好几次,导致我最后好像也忘了加Optional了 \狗头