做网站需要买ip地址吗,长春网站上排名,引流app推广软件,丽水建设公司网站23. 合并K个升序链表
给你一个链表数组#xff0c;每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中#xff0c;返回合并后的链表。
示例 1#xff1a;
输入#xff1a;lists [[1,4,5],[1,3,4],[2,6]] 输出#xff1a;[1,1,2,3,4,4,5,6] 解释#xf…23. 合并K个升序链表
给你一个链表数组每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中返回合并后的链表。
示例 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.length 0 k 10^4 0 lists[i].length 500 -10^4 lists[i][j] 10^4 lists[i] 按 升序 排列 lists[i].length 的总和不超过 10^4
代码
// 分治
func mergeKLists(lists []*ListNode) *ListNode {length : len(lists)if length 0 {return nil}if length 1 {return lists[0]}// 分而治之return mergeTwoLists(mergeKLists(lists[:length/2]), mergeKLists(lists[length/2:]))
}// 合并两个有序链表
func mergeTwoLists(list1, list2 *ListNode) *ListNode {if list1 nil {return list2}if list2 nil {return list1}if list1.Val list2.Val {list1.Next mergeTwoLists(list1.Next, list2)return list1} else {list2.Next mergeTwoLists(list1, list2.Next)return list2}
}
