目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
合并N个有序链表
访问量:1187
一、简介
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
要求: 空间复杂度 O(n),时间复杂度 O(n)
案例1:
输入: [{1,2,3},{4,5,6,7}] 返回值: {1,2,3,4,5,6,7}
二、实现
思路:因为N个链表是有序的,比较N个链表第一个节点值,找出最小值,将最小值所在链表往后移动一位,最后将最小值插入到返回链表中。
/* * type ListNode struct{ * Val int * Next *ListNode * } */ /** * * @param lists ListNode类一维数组 * @return ListNode类 */ func mergeKLists( lists []*ListNode ) *ListNode { // write code here if len(lists) == 0 { return nil } var head = new(ListNode) p := head for { nextNode := getMinNode(lists) if nextNode == nil { break } p.Next = nextNode p = nextNode } return head.Next } // 找出最小节点 func getMinNode(lists []*ListNode ) *ListNode { var minIndex = 0 for k,item := range lists { if item == nil { // 排除已为空的链表 continue } if lists[minIndex] == nil { // 设置默认值 minIndex = k continue } if item.Val < lists[minIndex].Val { // 比较 minIndex = k } } if lists[minIndex] == nil {// 代表链表已经没有节点了 return nil } minNode := lists[minIndex] lists[minIndex] = lists[minIndex].Next // 被选中的链表往后移动一位 minNode.Next = nil return minNode }
题目来源牛客
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助