首页 > 其他分享 >【刷题笔记】23. Merge k Sorted Lists

【刷题笔记】23. Merge k Sorted Lists

时间:2023-08-16 13:32:28浏览次数:30  
标签:return 23 Lists Next Merge l2 lists l1 ListNode

题目

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example :

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

题目大意

合并 K 个有序链表

解题思路

借助分治的思想,把 K 个有序链表两两合并即可。相当于是第 21 题的加强版。

参考代码

package leetcode

// ListNode define
type ListNode = structures.ListNode

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
	length := len(lists)
	if length < 1 {
		return nil
	}
	if length == 1 {
		return lists[0]
	}
	num := length / 2
	left := mergeKLists(lists[:num])
	right := mergeKLists(lists[num:])
	return mergeTwoLists1(left, right)
}

func mergeTwoLists1(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	if l1.Val < l2.Val {
		l1.Next = mergeTwoLists1(l1.Next, l2)
		return l1
	}
	l2.Next = mergeTwoLists1(l1, l2.Next)
	return l2
}

标签:return,23,Lists,Next,Merge,l2,lists,l1,ListNode
From: https://blog.51cto.com/u_16110811/7106780

相关文章

  • 2023年Java学习路线,23分钟视频讲解,快速掌握Java课程体系
    自学Java开发并非易事,特别是当你刚开始学习时,需要面对的困难似乎比预期的要多得多。但是,如果你有一个系统的学习路线和计划,并注重实践,那么你将会逐渐掌握Java,有效的提高学习效率。深知大家自学Java的苦,苦于没有系统的知识体系,不知道该学什么?看哪个视频比较好?因此,老杜精心录制了一版......
  • IDEA 2023.2 最新安装使用教程(附激活码,亲测好用)
    申明:本教程IntelliJIDEA补丁、激活码均收集于网络,请勿商用,仅供个人学习使用,如有侵权,请联系作者删除。若条件允许,希望大家购买正版!PS:本教程最新更新时间:2023年7月28日,持续更新,收藏防失联哟说明本教程适用于JetBrains全系列产品,包括IDEA、Pycharm、WebStorm、Phpstorm、Da......
  • 2023牛客暑期多校训练营8
    A.AliveFossils纯模拟没啥好说的map<string,int>mp;voidsolve(){intn;cin>>n;for(inti=1;i<=n;i++){intt;cin>>t;while(t--){strings;cin>>s;mp[s]++;}}......
  • [速报]2023-08-16: 发现Ubuntu网易云音乐几乎不能用了
    目录Ubuntu不能用Manjaro的也不能官网下载页替代方案yesplaymusicwineAUR仓库里的软件包Ubuntu不能用操作系统Ubuntu22.04.3网易云版本:iinetease-cloud-music1.2.1amd64Neteaseclou......
  • 2023“钉耙编程”中国大学生算法设计超级联赛(9)- 1003 Reasoning 题解
    题目翻译基本符号有一推理系统,其中有这些符号:括号\((\)和\()\);逻辑连接词\(\lnot\)和\(\rightarrow\);全称量词\(\forall\);变量\(u\simz\);常量\(a\sime\);函数\(f\simh\);谓词\(P\simT\)。这些符号是构成系统的基础,他们之间能够组合出一些其他概念:项(term......
  • 2023-2029全球铒YAG激光器行业调研及趋势分析报告
     2022年全球铒YAG激光器市场规模约亿元,2018-2022年年复合增长率CAGR约为%,预计未来将持续保持平稳增长的态势,到2029年市场规模将接近亿元,未来六年CAGR为%。从核心市场看,中国铒YAG激光器市场占据全球约%的市场份额,为全球最主要的消费市场之一,且增速高于全球。2022年市场规模约......
  • 2023-2029全球工业激光清洁行业调研及趋势分析报告
     2022年全球工业激光清洁市场规模约亿元,2018-2022年年复合增长率CAGR约为%,预计未来将持续保持平稳增长的态势,到2029年市场规模将接近亿元,未来六年CAGR为%。从核心市场看,中国工业激光清洁市场占据全球约%的市场份额,为全球最主要的消费市场之一,且增速高于全球。2022年市场规模......
  • 2023-2029全球激光清洗装置行业调研及趋势分析报告
     2022年全球激光清洗装置市场规模约亿元,2018-2022年年复合增长率CAGR约为%,预计未来将持续保持平稳增长的态势,到2029年市场规模将接近亿元,未来六年CAGR为%。从核心市场看,中国激光清洗装置市场占据全球约%的市场份额,为全球最主要的消费市场之一,且增速高于全球。2022年市场规模......
  • 2023-2029全球家用养生壶行业调研及趋势分析报告
     2022年全球家用养生壶市场规模约亿元,2018-2022年年复合增长率CAGR约为%,预计未来将持续保持平稳增长的态势,到2029年市场规模将接近亿元,未来六年CAGR为%。从核心市场看,中国家用养生壶市场占据全球约%的市场份额,为全球最主要的消费市场之一,且增速高于全球。2022年市场规模约亿......
  • 2023下半年产品经理国际认证NPDP8月19日线上开班
    产品经理国际资格认证NPDP是新产品开发方面的认证,集理论、方法与实践为一体的全方位的知识体系,为公司组织层级进行规划、决策、执行提供良好的方法体系支撑。  【认证机构】 产品开发与管理协会(PDMA)成立于1979年,是全球范围内产品开发与管理专业人士最杰出的倡导者,协助个人、企业......