【每天一道算法题】合并两个排序的链表
2023-04-18 16:14:04 时间
本专栏将会从基础开始,循序渐进,每天刷一道算法题,也请大家多多支持。数据结构虽然难,但只要肯坚持,一定能学好,希望大家都能够从中获益。
专栏地址: 每天一道算法题专栏 数据结构专栏
在线刷题网站:牛客网
准备好了吗
Let’s go!
前言
- 推荐给大家一款在线刷题神器,牛客网:刷题神器跳转链接
- 目前大厂的招聘都需要手撕代码,例如华为、腾讯等,该网站不仅可以在线编程模拟考试环境,熟悉考试流程,而且可以提升自己的代码能力与核心竞争力。
- 网站中不仅有算法入门及进阶教程,而且会将常见算法进行分类练习,例如链表篇、二叉树篇、堆/栈/队列以及递归和动态规划篇
- 除了刷算法题,还可以系统地学习其他知识,例如SQL篇、Python篇、HTML/CSS、JS篇、SHELL篇、名企真题、Verilog篇等,如下图所示:
Q1:反转链表
👀问题描述
题目来源:牛客网
✏️ 思路解析与题解
解法一,新建一个链表和一个哨兵节点(因为有去无回,需要哨兵节点来记录头节点的位置),遍历两个有序链表list1和list2,因为需要升序,那么谁小取谁做新链表的下一个节点,取谁的节点就往后移位,直到尾部null。
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1==null){
return list2;
}
if(list2==null){
return list1;
}
ListNode result = new ListNode(-1);
ListNode guard = result;//哨兵节点,很重要
while(true){
if(list1 == null && list2 == null){//全部取完了,可以结束了。
break;
}
if(list1==null){//list1取完了,后面的全部取list2的。
result.next = list2;
list2 = list2.next;
result = result.next;
}else if(list2 == null){//list2取完了,后面全部取list1的。
result.next = list1;
list1 = list1.next;
result = result.next;
}else if(list1.val<=list2.val){//和数组一样,谁小取谁的
result.next = list1;
list1 = list1.next;
result = result.next;
}else if(list1.val>list2.val){//和数组一样,谁小取谁的
result.next = list2;
list2 = list2.next;
result = result.next;
}
}
return guard.next;
}
解法二,对解法一进行优化,观察到,如果想用尽一个链表,那么直接指向它的头节点就行了,省去解法一中,取剩余节点的步骤。
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1==null){
return list2;
}
if(list2==null){
return list1;
}
ListNode result = new ListNode(-1);
ListNode guard = result;
while(list1!=null && list2!=null){
if(list1.val<=list2.val){//同解法一
result.next = list1;
list1 = list1.next;
result = result.next;
}else if(list1.val>list2.val){//同解法一
result.next = list2;
list2 = list2.next;
result = result.next;
}
}
if(list1==null){//优化点,剩下的节点全部取list2
result.next = list2;
}
if(list2==null){//优化点,剩下的节点全部取list1
result.next = list1;
}
return guard.next;
}
}
解法三, 使用递归,思想是:每次都取list1和list2的头节点进行比较,谁小谁当头节点,然后继续往后比较,这个步骤每一步都是一样的。
public ListNode Merge(ListNode list1,ListNode list2) {
//退出条件
if(list1==null){
return list2;
}
//退出条件
if(list2==null){
return list1;
}
ListNode guard = null;
//谁小谁当头结点,然后继续重复这个步骤
if(list1.val>=list2.val){
guard = list2;
guard.next = Merge(list1,list2.next);
}else{
guard = list1;
guard.next = Merge(list1.next,list2);
}
return guard;
}
点击如下链接进行跳转注册,开启你的从入门到精通的学习之路吧:
牛客网在线OJ
这里不仅有题库练习,而且包含面试和求职专区,在题库区中含有各个大公司的公司真题,如字节、腾讯、美团、阿里、百度、华为或者其他你想面试的公司,如下图所示:
在专项练习区中,你可以根据你的薄弱点进行针对性地练习,例如数组、字符串、链表、栈、队列、树、图、堆的题,如下图所示:
针对一些计算机基础知识,还涉及涉及模式、网络基础、数据库、操作系统等专项练习,让你巩固基础知识,在面试中侃侃而谈:
同时,还可以在线学习编程语言,免去配置环境的困扰,并且可以查漏补缺,早日收获大厂offer。
相关文章
- Consul 基础10
- Nvidia「艺术家神器」GauGAN发布第二代!训练超1000万张图片,两个词就能生成风景画
- 元宇宙六大技术全景图
- 玩桥牌,八位人类世界冠军,都输给了AI
- 实现多级缓存的架构设计方案
- 清华博士提出「Chiplet精算师」登顶会!越接近摩尔极限,多芯片集成越划算
- 90行代码!大一学生自学编程,自创搜题网站,已在GitHub开源
- Meta 拒绝使用高通芯片,并质疑其配套软件不够成熟
- 新一代数据基础设施:数据智能平台(附下载)
- 被奖12万!凌晨发现实验室漏水,中科大5学生踹门救下2400万设备和九章三号
- Transformer 自然语言处理简介
- 开价20w美元,这家公司想买下你的脸!不限性别年龄,预计2023年投入机器人使用
- Gartner公布首个SSE魔力象限排名
- 众筹十万美元搞火箭,搞研发全靠志愿者!这个“草根”航天组织已经开启载人测试
- 敏捷开发:从理论到团队落地
- 20年老码农分享20条编程经验,你pick哪些?
- 人工智能,“抛弃”真实数据集?
- 实战 | OpenCV如何将不同轮廓合并成一个轮廓(附源码)
- 认识ArcGIS Pro
- 谷歌下一代AI架构、Jeff Dean宣传大半年的Pathways终于有论文了