后端开发刷题 | 合并k个已排序的链表

描述

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围:节点总数 0≤n≤5000,每个节点的val满足 ∣val∣<=1000

要求:时间复杂度 O(nlogn)

示例1

输入:

[{1,2,3},{4,5,6,7}]

返回值:

{1,2,3,4,5,6,7}

示例2

输入:

[{1,2},{1,4,5},{6}]

返回值:

{1,1,2,4,5,6}

思路分析:

归并排序思想

知识点1:双指针

双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个指针(特殊情况甚至可以多个),两个指针或是同方向访问两个链表、或是同方向访问一个链表(快慢指针)、或是相反方向扫描(对撞指针),从而达到我们需要的目的。

知识点2:分治

分治即“分而治之”,“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题,子问题继续按照这样划分,直到问题可以被轻易解决;“治”指的是将子问题单独进行处理。经过分治后的子问题,需要将解进行合并才能得到原问题的解,因此整个分治过程经常用递归来实现。

对于这k个链表,就相当于上述合并阶段的k个子问题,需要划分为链表数量更少的子问题,直到每一组合并时是两两合并,然后继续往上合并,这个过程基于递归:

  • 终止条件: 划分的时候直到左右区间相等或左边大于右边。
  • 返回值: 每级返回已经合并好的子问题链表。
  • 本级任务: 对半划分,将划分后的子问题合并成新的链表。

具体做法:

  • step 1:从链表数组的首和尾开始,每次划分从中间开始划分,划分成两半,得到左边n/2个链表和右边n/2个链表。
  • step 2:继续不断递归划分,直到每部分链表数为1.
  • step 3:将划分好的相邻两部分链表,按照两个有序链表合并的方式合并,合并好的两部分继续往上合并,直到最终合并成一个链表。

图示:

alt

代码:

import java.util.*;public class Solution {//两个链表合并函数public ListNode merge(ListNode list1,ListNode list2){//一个已经为空了,直接返回另一个if(list1==null){return list2;}if(list2==null){return list1;}//加一个表头ListNode head=new ListNode(0);ListNode cur=head;//两个链表都要不为空while(list1!=null&&list2!=null){//取较小值的节点if(list1.val>list2.val){cur.next=list2;//只移动取值的指针list2=list2.next;}else{cur.next=list1;//只移动取值的指针list1=list1.next;}//指针后移,为下一次循环做准备cur=cur.next;}//哪个链表还有剩,直接连在后面if(list1!=null){cur.next=list1;}if(list2!=null){cur.next=list2;}//返回值去掉表头return head.next;}//划分合并区间函数public ListNode divideMerge(ArrayList<ListNode> lists,int left,int right){if(left>right){return null;//中间一个的情况}else if(left==right){return lists.get(left);}//从中间分成两段,再将合并好的两段合并int mid=(left+right)/2;return merge(divideMerge(lists,left,mid),divideMerge(lists,mid+1,right));}/*** * @param lists ListNode类ArrayList * @return ListNode类*/public ListNode mergeKLists (ArrayList<ListNode> lists) {//k个链表归并排序return divideMerge(lists,0,lists.size()-1);}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/406439.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【数据结构】二叉树的深度理解

&#x1f36c;个人主页&#xff1a;Yanni.— &#x1f308;数据结构&#xff1a;Data Structure.​​​​​​ &#x1f382;C语言笔记&#xff1a;C Language Notes 前言 在之前学习了二叉树的基本概念&#xff0c;但二叉树有着更深入知识理解&#xff0c;这篇文章可以帮助大…

使用Obsidian实现Anki快速制卡

文章目录 前言准备双双启用遇到问题查看是什么问题解决问题 开始使用使用前的一些设置快速制卡 前言 我现在使用 Anki 的同时也使用 Obsidian&#xff0c;正好可以通过插件来让这两个十分好用的软件实现联动。 在 Obsidian 中实现 Anki 的快速制卡。 准备 首先要在这两个软…

原型制作 | 歌词与进度条的位置呼应

在之前的案例里面咱们做过了歌词滚动的效果&#xff0c;具体效果是这样的&#xff0c;点击播放按钮&#xff0c;歌词开始滚动&#xff1b;点击暂停按钮&#xff0c;歌词停止滚动&#xff0c;再次点击播放&#xff0c;歌词会继续滚动&#xff1b;一直播放直到结束&#xff0c;歌…

java常见面试题汇总

&#x1f30f;个人博客主页&#xff1a;意疏-CSDN博客 希望文章能够给到初学的你一些启发&#xff5e; 如果觉得文章对你有帮助的话&#xff0c;点赞 关注 收藏支持一下笔者吧&#xff5e; 阅读指南&#xff1a; 开篇说明一、封装 继承 多态1.封装2.继承3.多态 二、什么是重载…

【前端】VUE 在线运行 模拟器 通过字符串动态渲染页面 可以灵活使用

【前端】VUE2 在线运行 模拟器 通过字符串动态渲染页面 可以灵活使用 <template><div><!-- 这里是动态组件--><component :is"component"></component><!-- 这里是动态组件--><br /><br /><br />可…

Gitlab添加ssh秘钥download项目

1. 查看 、设置 git 用户名和邮箱 git config user.namegit config user.email git config --global user.name 用户名git config --global user.email 邮箱 2. 查看本地是否有ssh秘钥 秘钥默认放在C:\Users\用户\.ssh\目录下&#xff0c;进入这个目录&#xff0c;如果有 …

elasticsearch的高亮查询三种模式查询及可能存在的问题

目录 高亮查询使用介绍 高亮参数 三种分析器 可能存在的查询问题 fvh查询时出现StringIndexOutOfBoundsException越界 检索高亮不正确 参考文档 高亮查询使用介绍 Elasticsearch 的高亮&#xff08;highlight&#xff09;可以从搜索结果中的一个或多个字段中获取突出显…

社区维修平台

TOC springboot0751社区维修平台 第一章 绪 论 1.1背景及意义 系统管理也都将通过计算机进行整体智能化操作&#xff0c;对于社区维修平台所牵扯的管理及数据保存都是非常多的&#xff0c;例如住户管理、社区公告管理、维修工管理、维修订单管理、接单信息管理、订单信息管…

谁将解锁储能的未来?迈威通信邀您共探EESA储能展的秘密

九月金秋&#xff0c;硕果盈枝&#xff0c;迈威通信诚挚邀请您共赴一场科技盛宴——第三届EESA储能展&#xff0c;时间锁定9月2日至4日&#xff0c;地点&#xff1a;国家会展中心(上海)&#xff0c;一场关于绿色能源、智慧储能的梦幻之旅即将启航&#xff01; 您准备好迎接未来…

利用大型语言模型协作提升甲状腺结节超声诊断的一致性和准确性| 文献速递-基于深度学习的癌症风险预测与疾病预后应用

Title 题目 Collaborative Enhancement of Consistency and Accuracy in US Diagnosis of Thyroid Nodules Using Large Language Models 利用大型语言模型协作提升甲状腺结节超声诊断的一致性和准确性 Background 背景 Large language models (LLMs) hold substantial …

Redis内存管理

Redis使用Jemalloc(默认编译)来进行内存的管理&#xff1a; Jemalloc将内存分成许多不同的区域&#xff0c;每个区域成为arena&#xff0c;areana之间相互独立。Jemalloc通过创建多个arena来减少线程申请内存的操作冲突。一般arena数量为cpu数量*4. arena以chunk为单位向操作…

FPGA 综合笔记

仿真时阻塞赋值和非阻塞赋值 Use of Non-Blocking Assignment in Testbench : Verilog Use of Non-Blocking Assignment in Testbench : Verilog - Stack Overflow non-blocking assignment does not work as expected in Verilog non-blocking assignment does not work a…

Python使用QtSide6(PyQt)编写界面

1、安装QtSide6 开始菜单cmd 创建虚拟环境 python -m venv env2 进入虚拟环境 call env2/scripts/activate 安装Pyside6 pip install Pyside6 2、设计Qt界面 打开designer.exe&#xff0c;设计界面 点击菜单【窗体】【View Python Code...】&#xff0c;点击【全部复制】…

HarmonyOs透明弹窗(选择照片弹窗样式)

1.鸿蒙中需要实现一个如下图的弹窗 2.由上图中可以得出&#xff0c;只需要三个Text组件依次向下排列&#xff0c;弹窗背景设置透明即可&#xff0c;弹窗代码如下(仅展示弹窗样式)&#xff1a; /**** 自定义选择图片弹窗** 外部定义需要导出*/ CustomDialog //自定义弹窗 export…

android13顶部状态栏里面调节背光,不隐藏状态栏面板

总纲 android13 rom 开发总纲说明 目录 1.前言 2.代码分析 3.修改方法 4.编译运行 5.彩蛋 1.前言 android13顶部状态栏里面调节背光,这个时候状态栏面板会被隐藏掉,有些需求就需要不隐藏这个面板。 2.代码分析 查找亮度条属性 id/brightness_slider ./frameworks/b…

TOMCAT入门到精通

目录 一 WEB技术 1.1 HTTP协议和B/S 结构 1.2 前端三大核心技术 1.2.1 HTML 1.2.2 CSS&#xff08;Cascading Style Sheets&#xff09;层叠样式表 1.2.3 JavaScript 二 WEB框架 2.2后台应用架构 2.2.1单体架构 2.2.2微服务 2.2.3单体架构和微服务比较 三 tomcat的…

2024Go语言面试宝典Golang零基础实战项目面试八股力扣算法笔记等

2024最新Golang面试八股文&#xff0c;以及各种零基础全套实战项目&#xff0c;经典力扣算法题以及常见的面试题型&#xff0c;大厂面试题。go语言面试必备。包括GO基础类、GO并发编程、GO RUNTIME、微服务、容器技术、Redis、MySQL、Linux、缓存、网络和操作系统、消息队列、分…

房产系统架构开发小程序分析

房产系统架构开发小程序在当前市场中具有显著的优势和潜力。以下是对房产小程序的分析&#xff1a; 用户需求满足&#xff1a;房产小程序通过提供楼盘信息查询、VR看房体验、购房流程指南等功能&#xff0c;满足用户对房产信息的需求&#xff0c;并提供更加便捷的用户体验 。…

NSSCTF练习记录:[SWPUCTF 2021 新生赛]crypto6

题目&#xff1a; 先转为base16 JZLVK6CNKRATKT2ENN2FUR2NGBGXSMDYLFWVC6SMKRAXOWLKKF2E6VCBO5HVISLXJZVEKMKPI5NGY再转base32 NWUxMTA5ODktZGM0My0xYmQzLTAwYjQtOTAwOTIwNjE1OGZl再转base64&#xff0c;得到答案 5e110989-dc43-1bd3-00b4-9009206158fe

如何使用GPT-SoVITSS生成各种角色的语言

百度网盘 请输入提取码 项目来自b站UP主花儿不哭 一&#xff0c;先除去背景声音————人生伴奏出去背景声音 1.下载后&#xff0c;按下面路径打开&#xff0c;打开文件beta&#xff0c;打开go-webui程序 回车&#xff0c;然后稍等一下&#xff0c;等待网页打开 2.勾选如下…