[LeetCode] 23.合并K个排序链表

题目

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

示例:

输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6 用时最短

class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: dummy = pre = ListNode(-1) nums = [] for node in lists: while node: nums.append(node) node = node.next for node in sorted(nums,key=lambda n:n.val): pre.next = node pre = pre.next return dummy.next

最小堆

from heapq import heapify, heappop class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: # 读取所有的节点值 h = [] for node in lists: while node: h.append(node.val) node = node.next # 构造一个最小堆 if not h: return None heapify(h) # 转换成最小堆 # 构造链表 root = ListNode(heappop(h)) curnode = root while h: nextnode = ListNode(heappop(h)) curnode.next = nextnode curnode = nextnode return root

分治解法

class Solution: def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode: l = ListNode(0) temp = l while l1 or l2: if not l1: temp.next = l2 break elif not l2: temp.next = l1 break v1 = l1.val v2 = l2.val if l1.val < v2 : temp.next = ListNode(v1) l1 = l1.next else: temp.next = ListNode(v2) l2 = l2.next temp = temp.next return l.next def mergeKLists(self, lists: List[ListNode]) -> ListNode: lens = len(lists) if not lens: return None elif lens == 1: return lists[0] elif lens ==2: return Solution.mergeTwoLists(lists[0],lists[1]) mid = lens//2 l1 = [] l2 = [] for i in range(mid): l1.append(lists[i]) for i in range(mid,lens): l2.append(lists[i]) return Solution.mergeTwoLists(self.mergeKLists(l1),self.mergeKLists(l2))

普通解法

class Solution: def mergeKLists(self, listss: List[ListNode]) -> ListNode: l = ListNode(0) temp = l lists = [] for node in listss: if node : lists.append(node) while lists: minval = lists[0].val index = 0 # minval = 8 for i in range(len(lists)): if lists[i].val < minval: minval, index = lists[i].val, i print('min:',minval, 'index:',index) temp.next = ListNode(minval) lists[index] = lists[index].next if not lists[index]: lists.remove(lists[index]) print('remove:',index) temp = temp.next return l.next

lambda相关

lambda作为一个表达式，定义了一个隐函数，上例的代码n为入口参数，n.val为函数体

最小堆相关

最小堆是一棵完全二叉树，非叶子结点的值不大于左孩子和右孩子的值。

分治相关

分治法得基本步骤： 　　step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

step3 合并：将各个子问题的解合并为原问题的解。

它的一般的算法设计模式如下： 　　Divide-and-Conquer(P ) 　　1. if |P|≤n0 　　2. then return(ADHOC(P )) 　　3. 将P分解为较小的子问题 P1 ,P2 ,…,Pk 　　4. for i←1 to k 　　5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi 　　6. T ← MERGE(y1,y2,…,yk) △ 合并子问题 　　7. return(T)

其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC (p )是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(p )求解。算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解。