Java-数据结构-链表-高频面试题(1)

在上一篇文章中,我们学习了链表中的"单向链表"但学可不代表就是学会了,能够运用链表的地方比比皆是,解题方法也是层出不穷,今天就让我们巩固一下"单向链表"的知识吧~

第一题:相交链表

📚 思路提示

想要判断链式结构中是否存在环,就要证明两者有相交,所以就要找到两者的相交点。而两个单链表的长度时常有所不同,所以遍历时就可能出现错过相交点的情况,因此我们最好想一个"特殊的起始点",即为"较长链表的中间结点,并且从该结点开始到最后的长度等于较短链表的长度"。

想要拿到这个结点并不难,我们只需要求出两个链表各自的长度,再求出链表长度的差值,这个差值为几,就让较长链表向后走几步,走完后较长链表剩下的部分链表长度,就正好等于较短链表的长度了~

图解

我们只需要注意,遍历完两个链表后仍然没有相交点即为"非相交链表"就好了~

📖 代码示例

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA = headA;int lena = 0;ListNode curB = headB;int lenb = 0;while(curA != null){curA = curA.next;lena++;}while(curB != null){curB = curB.next;lenb++;}int num = Math.max(lena,lenb) - Math.min(lena,lenb);if(lena > lenb){while(num-- > 0){headA = headA.next;}}else {while(num-- > 0){headB = headB.next;}}while(headA != headB){headA = headA.next;headB = headB.next;if(headA == null || headB == null){return null;}}return headA;}
}

第二题:反转链表

📚 思路提示想要做到指定区间内反转单链表,我们需要先学会如何整体反转单链表

关于单链表我们知道,结点只能一直向前走,不能往回走,而且想要两个结点互换位置,就代表至少需要两个结点来进行操作,而我们不仅仅想交换两个结点,交换后我们还需要让结点继续往后走,直到将需要的范围全部进行反转才可以。

而想要交换后再让结点继续往后走,只用两个结点就会出现问题了,比如上图中我们想将" 2 "和" 3 "的位置相互交换,所以交换后" 3 "的下一个就应该是" 2 ",而这样就会出现"丢失原链表"的问题,所以我们还需要第三个链表用来确保结点能够正常的后移~

(为防止访问越界,我们可以将第三个链表放入循环内部定义)

我们来演示一下整体反转单链表是何种过程。

图解

这就是整体反转单链表的全过程了,还是比较好理解的~

(记得把反转链表的末尾加上null)

📖 代码示例

class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null){return head;}ListNode cur = head;ListNode curn = head.next;while(curn != null){ListNode curN = curn.next;curn.next = cur;cur = curn;curn = curN;}head.next = null;return cur;}
}

第三题:反转链表 II

📚 思路提示:学会了链表的反转之后,我们来尝试一下这道题,本质上虽然还是反转链表,但是相比上一题,这一题需要考虑的就比较多了。

首先我们先设置一个计数器,从头开始遍历链表,每移动一个结点,计数器相应加一,直到计数器与left相等时,我们开始反转链表~并且在反转链表的途中,left还要时刻加一,直到计数器与right相等时,我们的反转链表工作结束~

(这里就不画图演示了,和上一题是一样的~)

还记得嘛?上一题虽然主要考察反转链表,但是就算会了反转链表,如果忘记了将 " head = null " 也还是没有用的~而 " head = null " 是因为将链表整体反转后,我们的尾结点就不再是之前的尾结点了,也正是因为如此,新的尾结点后面便不是 "null" ,而是" 原链表中第二个结点 ",这是因为 "新的尾结点是原来的头结点,原头结点的next就是第二个结点"~ 

上面就是一种情况,所代表的是"从头到尾全部反转",即"left == 1 && right == 链表长度"

(时间复杂度为O(n)的情况下无法拿到链表长度,所以我们可以通过"反转列表尾结点的next是否为null"来确认right是否为链表长度~)

而就这两种因素来说,能够组成四种不同的组合,这也就是解题的关键了。

图解

(以下对应操作中,lcur代表"反转链表首结点的前一结点"Lcur代表"反转链表首结点")

📕 (left == 1 && curn != null)

📖 对应操作head.next = curn;

📕 (left != 1 && curn == null)

📖 对应操作lcur.next = cur;

                        Lcur.next = null;

📕 (left != 1 && curn != null)

📖 对应操作lcur.next = cur;

                        Lcur.next = curn;

📕 (left == 1 && curn == null)

📖 对应操作Lcur.next = null;

📖 代码示例

class Solution {public ListNode reverseBetween(ListNode head, int m, int n) {if (head == null || head.next == null || m == n) {return head;}int left = 1;ListNode cur = head;// 用于保存反转链表首结点的前一结点ListNode lcur = null;// 用于保存反转链表首结点ListNode Lcur = null;while (cur != null && left != m) {//获取反转链表首结点的前一结点if (left == m - 1) {lcur = cur;}cur = cur.next;left++;}//获取反转链表首结点Lcur = cur;ListNode curn = cur.next;while (curn != null && left != n) {ListNode curN = curn.next;curn.next = cur;cur = curn;curn = curN;left++;}if(m == 1 && curn != null){head.next = curn;}else if(m != 1 && curn == null){lcur.next = cur;Lcur.next = null;}else if(m != 1 && curn != null){lcur.next = cur;Lcur.next = curn;}else{Lcur.next = null;}if(m != 1){return head;}return cur;}
}

第四题:链表的中间结点

📚 思路提示:这题要求的是中间结点,相信聪明的你稍微思考一下就有思路咯~对的,其实就是使用快慢指针我们只需要创建两个结点," slow = head " 和 " fast = head ",当 fast 走到末尾的时候,slow所处的位置就是中间结点了。

图解

📖 代码示例

class Solution {public ListNode middleNode(ListNode head) {if(head == null){return null;}ListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;}return slow;}
}

第五题:链表的回文结构

📚 思路提示回文结构相信对大家来说都不陌生吧~这是一种" 向前和向后读都相同的序列 "。

或许大家心里想的已经很简单了吧~可能想着"全反转一遍,再和原来的链表对比一下~",其实并没有这么简单,我们注意,题目要求我们设计时间复杂度为O(n)的解题方法这也就代表我们必须只遍历一次链表就判断出它是否为"回文结构"。

虽然不能"全反转一遍",但反转在这题中确实是非常至关重要的一步~相信经过上两道题的练习,大家已经能够流畅的反转链表了~

因为回文结构 "从前和向后读都相同",也就代表了后半部分的反转链表应该等于前半部分的链表,所以此题中我们需要反转的部分是"链表的后半部分"~

而想要拿到后半部分,我们就要找到中间节点这也是我们的上一题呀~这回思路通畅了吧~看看图解吧!

图解

📕 寻找中间结点

📕 反转链表

这里大家就能看出一些问题了~没错,奇数个结点和偶数个结点的情况是不同的~所以我们对比的时候采用这这样的策略:

📕 最后对前后链表进行对比时,将最后一对结点拿出循环单独进行对比

📖 代码示例

class Solution {public boolean isPalindrome(ListNode head) {if(head == null || head.next == null){return true;}ListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;}//保存初始反转结点ListNode c = slow;ListNode cur = slow.next;while(cur != null){ListNode curn = cur.next;cur.next = slow;slow = cur;cur = curn;}//将新的尾结点next = nullc.next = null;//保存反转后反转链表表头cur = slow;//slow.next != null 是将最后一对结点保留//用于后续对"奇数个结点"和"偶数个结点"进行区分while(slow.next != null){//值不相同则不是回文链表if(head.val != slow.val){return false;}slow = slow.next;head = head.next;}//head == cur 代表奇数个结点//head.val == slow.val 代表偶数个结点if(head == cur || head.val == slow.val){return true;}return false;}
}

第六题:环形链表

📚 思路提示:这题并不难,我们只需要创建一对快慢指针,在两者都不等于null的情况下一直循环,如果在某一刻两个结点相遇了,就代表这是一个环形链表~

图解

📖 代码示例

public class Solution {public boolean hasCycle(ListNode head) {if(head == null){return false;}ListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;if(slow == fast){return true;}}return false;}
}

第七题:环形链表 II

📚 思路提示:这题感觉属于是一个数学题...我们直接看图解:

图解

而最后得到的 X = Y 则代表"相遇点到入口的距离" = "头结点到入口的距离",这样一来问题也就迎刃而解了,我们只需要找到两个结点的相遇点,然后相遇点的结点与头结点同时一步一步的移动,直到两者相遇,这个结点就是入口结点~

📖 代码示例

public class Solution {public ListNode detectCycle(ListNode head) {if(head == null || head.next == null){return null;}ListNode slow = head.next;ListNode fast = head.next.next;while(slow != fast){if(fast == null || fast.next == null){return null;}slow = slow.next;fast = fast.next.next;}slow = head;while(slow != fast){slow = slow.next;fast = fast.next;}return slow;}
}

那么这次关于链表的练习题就为大家分享到这里啦,作者能力有限,如果有讲得不清晰或者不正确的地方,还请大家在评论区多多指出,我也会虚心学习的!那我们下次再见哦~

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

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

相关文章

低空管控技术-无人机云监视技术详解!

一、无人机监听技术的原理 无人机监听技术主要依赖于射频(RF)探测、光学和红外传感器等技术手段。这些技术通过被动监听和监测无人机与飞行员(或控制器)之间的通信链路传输,以确定无人机的位置,甚至在某些…

STM32-WWDG/IWDG看门狗

WWDG/IWDG一旦开启不能关闭,可通过选项字节在上电时启动硬件看门狗,看门狗计数只能写入不能读取。看门狗启用时,T6bit必须置1,防止立即重置。 一、原理 独立看门狗-超时复位 窗口看门狗-喂狗(重置计数器,…

【形式篇】年终总结怎么写:PPT如何将内容更好地表现出来

——细节满满,看完立马写出一篇合格的PPT 总述 形式服务于内容,同时合理的形式可以更好地表达和彰显内容 年终总结作为汇报型PPT,内容一定是第一位的,在内容篇(可点击查看)已经很详细地给出了提纲思路,那如何落实到…

分享3个国内使用正版GPT的网站【亲测有效!2025最新】

1. molica 传送入口:https://ai-to.cn/url/?umolica 2. 多帮AI 传送入口:https://aigc.openaicloud.cn?inVitecodeMYAAGGKXVK 3. 厉害猫 传送入口:https://ai-to.cn/url/?ulihaimao

使用免费内网穿透(p2p)网络环境搭建小型文件管理服务器(简单操作)

目录 前言 “节点小宝” 使用环境: 应用场景: 准备工作 安装 …

在macOS上安装MySQL

macOS的MySQL有多种不同的形式: 1、本机包安装程序,它使用本机macOS安装程序(DMG)引导您完成MySQL的安装。有关详细信息,请参阅第2.4.2节,“使用本机包在macOS上安装MySQL”。您可以将包安装程序与macOS一…

汽车信息安全 -- S32K1如何更新BOOT_MAC

目录 1.安全启动模式回顾 2.为什么要讨论BOOT_MAC 3.S32K1如何更新? 1.安全启动模式回顾 之前提到过,S32K1系列提供了Crypto Service Engine硬件加密模块(简称CSEc),大家可以通过该芯片系统寄存器SDID.FEATURES(System Device Identification Register)来判断自己的片子…

STM32-笔记35-DMA(直接存储器访问)

一、什么叫DMA? DMA(Direct Memory Access,直接存储器访问)提供在外设与内存、存储器和存储器之间的高速数据传输使用。它允许不同速度的硬件装置来沟通,而不需要依赖于CPU,在这个时间中,CPU对于…

从零开始开发纯血鸿蒙应用之实现起始页

从零开始开发纯血鸿蒙应用 一、前言二、主要页面三、应用起始页四、MainPageContent 实现1、一级结构2、二级结构2.1、EmptyContent2.2、FileListContent2.2.1、ViewAction:2.2.2、EditAction2.2.3、DeleteAction2.2.4、ShareAction 五、载入起始页的时机五、总结 一…

Pytorch初学

创建虚拟环境 python控制台,jupyter notebook,python文件运行的差异,后续结合使用三者。 jupter主要可以对代码进行分割单独运行,主要做一些探索性工作。 数据集的常见存储模式 1、以标签命名图像。 2、单独存储图像的地址。 加载数据集…

Anthropic 的人工智能 Claude 表现优于 ChatGPT

在人工智能领域,竞争一直激烈,尤其是在自然语言处理(NLP)技术的发展中,多个公司都在争夺市场的主导地位。OpenAI的ChatGPT和Anthropic的Claude是目前最具影响力的两款对话型AI产品,它们都能够理解并生成自然…

【Linux系列】并发与顺序执行:在 Linux 脚本中的应用与选择

💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

更换WordPress主题的基础知识及注意事项

更换WordPress主题是优化和升级网站的重要步骤,不仅能够增强网站的视觉效果,还能改进用户体验并提高网站性能。然而,在进行该操作时,必须格外谨慎,避免数据丢失或功能失调的风险。本文将介绍在更换主题前需要采取的基本…

conda指定路径安装虚拟python环境

DataBall 助力快速掌握数据集的信息和使用方式,会员享有 百种数据集,持续增加中。 需要更多数据资源和技术解决方案,知识星球: “DataBall - X 数据球(free)” -------------------------------------------------------------…

HTML 迷宫游戏

HTML 迷宫游戏 相关资源文件已经打包成压缩文件,可双击index.html直接运行程序,且文章末尾已附上相关源码,以供大家学习交流,博主主页还有更多Python相关程序案例,秉着开源精神的想法,望大家喜欢&#xff0…

PDFMathTranslate: Star13.8k,一款基于AI的PDF文档全文双语翻译PDF文档全文双语翻译,保留格式神器,你应该需要它

嗨,大家好,我是小华同学,关注我们获得“最新、最全、最优质”开源项目和高效工作学习方法 PDFMathTranslate是一个开源项目,旨在为用户提供便捷的PDF科学论文翻译解决方案。它不仅能够翻译文本,还能保留公式、图表、目…

调整Python+Pytest+Allure+Yaml+Pymysql框架中需要执行的用例顺序

当pytest框架中有时时候会因为用例的前后关联关系需要调整用例执行顺序时则可以跟进具体的要求调整pytest.ini配置文件中执行用例文件夹的前后顺序 当如果是需要调整某个文件夹中用例的执行顺序时,则跟进具体的文件调整对应testcases中test_*.py文件中的执行顺序

毕业项目推荐:基于yolov8/yolov5/yolo11的动物检测识别系统(python+卷积神经网络)

文章目录 概要一、整体资源介绍技术要点功能展示:功能1 支持单张图片识别功能2 支持遍历文件夹识别功能3 支持识别视频文件功能4 支持摄像头识别功能5 支持结果文件导出(xls格式)功能6 支持切换检测到的目标查看 二、数据集三、算法介绍1. YO…

BloombergGPT: A Large Language Model for Finance——面向金融领域的大语言模型

这篇文章介绍了BloombergGPT,一个专门为金融领域设计的大语言模型(LLM)。以下是文章的主要内容总结: 背景与动机: 大语言模型(如GPT-3)在多个任务上表现出色,但尚未有针对金融领域的…

CS·GO搬砖流程详细版

说简单点,就是Steam买了然后BUFF上卖,或许大家都知道这点,但就是一些操作和细节问题没那么明白。我相信,你看完这篇文章以后,至少会有新的认知。 好吧,废话少说,直接上实操! 首先准…