算法-分治 23. 合并 K 个升序链表 2024-03-20 默认分类 暂无评论 266 次阅读 [LeetCode-23. 合并 K 个升序链表](https://leetcode.cn/problems/merge-k-sorted-lists/description/?envType=study-plan-v2&envId=top-interview-150 "LeetCode-23. 合并 K 个升序链表") 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 = [[]] 输出：[] ```Go func mergeTwoLists(list1, list2 *ListNode) *ListNode { dummy := &ListNode{} // 用哨兵节点简化代码逻辑 cur := dummy // cur 指向新链表的末尾 for list1 != nil && list2 != nil { if list1.Val < list2.Val { cur.Next = list1 // 把 list1 加到新链表中 list1 = list1.Next } else { // 注：相等的情况加哪个节点都是可以的 cur.Next = list2 // 把 list2 加到新链表中 list2 = list2.Next } cur = cur.Next } // 拼接剩余链表 if list1 != nil { cur.Next = list1 } else { cur.Next = list2 } return dummy.Next } func mergeKLists(lists []*ListNode) *ListNode { m := len(lists) if m == 0 { // 注意输入的 lists 可能是空的 return nil } if m == 1 { // 无需合并，直接返回 return lists[0] } left := mergeKLists(lists[:m/2]) // 合并左半部分 right := mergeKLists(lists[m/2:]) // 合并右半部分 return mergeTwoLists(left, right) // 最后把左半和右半合并 } ``` 标签: 算法 转载请注明文章来源 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭