[leetcode] 23. 合并K个升序链表

[leetcode] 23. 合并K个升序链表

Description

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。 示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6

示例 2：

输入：lists = []输出：[]

示例 3：

输入：lists = [[]]输出：[]

提示：

k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4

分析

题目的意思是：K个升序链表的合并，用分治法，没想到python写出来的代码还是挺简洁的。

代码

# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def merge(self,l1,l2): root = ListNode(None) p = root while(l1 and l2 ): if(l1.val<=l2.val): tmp_node = ListNode(l1.val) l1=l1.next else: tmp_node = ListNode(l2.val) l2=l2.next p.next=tmp_node p=p.next while(l1): tmp_node = ListNode(l1.val) p.next=tmp_node p=p.next l1=l1.next while(l2): tmp_node = ListNode(l2.val) p.next=tmp_node p=p.next l2=l2.next return root.next def solve(self,lists): if(len(lists)==1): return lists[0] elif(len(lists)==2): return self.merge(lists[0],lists[1]) else: middle=len(lists)//2 return self.merge(self.solve(lists[:middle]),self.solve(lists[middle:])) def mergeKLists(self, lists: List[ListNode]) -> ListNode: if(len(lists)==0): return None return self.solve(lists)

参考文献

​​[LeetCode]DC​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。