广西南宁市网站建设服务中心/关键词排名查询
目录
引言
面试题01:返回倒数第k个节点
题目描述:
思路分析:
代码展示:
面试题02:链表的回文结构
题目描述:
描述
思路分析:
代码展示:
面试题03:相交链表
题目描述:
思路分析:
代码展示:
小结:
引言
这次的题均来自力扣和牛客有关链表的经典面试题,代码只会展示最优的解法,之前发布过单链表的经典算法--单链表经典算法-CSDN博客,大家可以先看看经典算法,再看这个面试题,会轻松很多,如果觉得这篇博客对你有帮助的话,一定要点赞关注哦!
面试题01:返回倒数第k个节点
--面试题 02.02. 返回倒数第 k 个节点 - 力扣(LeetCode)
题目描述:
实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。
注意:本题相对原题稍作改动
示例:
输入: 1->2->3->4->5 和 k = 2 输出: 4说明:
给定的 k 保证是有效的。
思路分析:
这道题最快的解题方法为快慢指针,大家可以先去看单链表经典算法-CSDN博客中的链表的中间节点.也就是定义两个指针,快指针先走k步,再让快慢指针同时走,直到快指针为NULL,两个指针之间恒定相差为k步,最后的慢指针即为倒数第k个节点.如下图所示:
代码展示:
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/int kthToLast(struct ListNode* head, int k){struct ListNode* fast = head, *slow = head;//快指针先走k步while(k--){fast = fast->next;}//同时走while(fast){fast = fast->next;slow = slow->next;}return slow->val;
}
面试题02:链表的回文结构
--链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
题目描述:
描述
对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。
给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。
测试样例:
1->2->2->1 返回:true
思路分析:
这道题主要难在它的空间复杂度要求为O(1),也就是不能在创建新的链表,所以重点从如何判断回文结构入手,我们不难发现,找到链表的中间节点,再将链表另一侧翻转,如果两边相同即为回文结构,如下图所示:
这里就涉及了两个算法,一个是找到链表的中间节点并返回,一个是翻转链表.这两个算法大家可以去看单链表经典算法-CSDN博客,哪里我详细讲解了这两个算法的实现,这里我就不多说了,直接给出代码:
代码展示:
找到链表的中间节点
struct ListNode* middleNode(struct ListNode* head) {//创建快慢指针ListNode*slow = head;ListNode*fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}
翻转链表
struct ListNode* reverseList(struct ListNode* head) {//判空if(head == NULL){return head;}//创建三个指针ListNode*n1,*n2,*n3;n1 = NULL,n2=head,n3=n2->next;while(n2){n2->next = n1;n1=n2;n2=n3;//n2没走完时,n3已经为空,要进行判空if(n3)n3 = n3->next;}return n1;
}
完整代码:
class PalindromeList {
public:struct ListNode* reverseList(struct ListNode* head) {//判空if(head == NULL){return head;}//创建三个指针ListNode*n1,*n2,*n3;n1 = NULL,n2=head,n3=n2->next;while(n2){n2->next = n1;n1=n2;n2=n3;//n2没走完时,n3已经为空,要进行判空if(n3)n3 = n3->next;}return n1;
}struct ListNode* middleNode(struct ListNode* head) {//创建快慢指针ListNode*slow = head;ListNode*fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}bool chkPalindrome(ListNode* A) {// write code herestruct ListNode* mid = middleNode(A);struct ListNode* rmid = reverseList(mid);while(rmid && A){if(rmid->val != A->val)return false;rmid = rmid->next;A = A->next;}return true;}};
面试题03:相交链表
--160. 相交链表 - 力扣(LeetCode)
题目描述:
给你两个单链表的头节点 headA
和 headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null
。
图示两个链表在节点 c1
开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
思路分析:
首先题目要求判断两个链表是否相交,若相交返回相交的起始节点,否侧返回NULL,那么第一个问题如何判断两个链表是否相交呢?其实很简单,遍历两个链表,找到两个链表的最后节点,若两个链表的最后节点相等,那么两个链表一定相交.难就难在如何返还相交起始节点的位置,因为两个链表相交之前的链表是不相等的,如果是相等的话,那我们就可以直接遍历,从这个角度出发,我们在之前判断是否相交时,求出两个链表的长度,因为后半段的长度两个链表一直,那么两个链表的长度差即为长链表领先的节点个数,让长链表先走长度差,再让两个链表同时走,这样就能找到起始相交的节点.如下图:
代码展示:
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA = headA, *curB = headB;int lenA = 0, lenB = 0;while(curA->next){curA = curA->next;++lenA;}while(curB->next){curB = curB->next;++lenB;}//尾节点不相交返回空if(curA != curB) return NULL;int gap = abs(lenA - lenB);struct ListNode* longList = headA, * shortList = headB;if(lenB > lenA){longList = headB;shortList = headA;}while(gap--){longList = longList->next;}while(longList != shortList){longList = longList->next;shortList = shortList->next;}return shortList;
}
小结:
这一个专题我准备分两期进行制作,后一期专门进行链表带环问题的讲解,如果觉得对你有帮助的家人们,记得点赞关注哦!
相关文章:

链表经典面试题01
目录 引言 面试题01:返回倒数第k个节点 题目描述: 思路分析: 代码展示: 面试题02:链表的回文结构 题目描述: 描述 思路分析: 代码展示: 面试题03:相交链表 题目描述: 思路分析: 代码展示: 小结: 引言 这次的题均来自力扣和牛客有关链表的经典面试题,代码只会展示…...

基于java的CRM客户关系管理系统的设计与实现(论文 + 源码 )
【免费】基于Java的CRM客户关系管理系统的设计和实现.zip资源-CSDN文库https://download.csdn.net/download/JW_559/89273409 基于Java的CRM客户关系管理系统的设计与实现 摘 要 随着互联网的高速发展,市场经济的信息化,让企业之间的竞争变得࿰…...

【动态规划-最长上升子序列模型part2】:拦截导弹、导弹防御系统、最长公共上升子序列【已更新完成】
1、拦截导弹 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。 某天,雷达捕捉到敌国的导弹来袭。 由于…...

Spring 如何解决 Bean 循环依赖
循环依赖解释 bean A 属性注入时依赖bean B ,并且bean B属性注入时也依赖bean A ,造成 bean A 和bean B 都无法完成初始化问题,形成了闭环。 注意 项目中存在Bean的循环依赖,是Bean对象职责划分不明确、代码质量不高的表现&#…...

【driver4】锁,错误码,休眠唤醒,中断,虚拟内存,tasklet
文章目录 1.互斥锁和自旋锁选择:自旋锁(开销少)的自旋时间和被锁住的代码执行时间成正比关系2.linux错误码:64位系统内核空间最后一页地址为0xfffffffffffff000~0xffffffffffffffff,这段地址是被保留的,如果…...

python之 函数相关知识解析
01 函数的注释与嵌套 1.函数的注释 函数的注释与普通注释的区别:用来说明当前函数的参数含义 param 参数名: 参数的注释信息 return: 函数的返回值 例如: def fun1(name):""":param name: 参数的注释信息:return: 函数的返回值"…...

监视器和显示器的区别,普通硬盘和监控硬盘的区别
监视器与显示器的区别,你真的知道吗? 中小型视频监控系统中,显示系统是最能展现效果的一个重要环节,显示系统的优劣将直接影响视频监控系统的用户体验满意度。 中小型视频监控系统中,显示系统是最能展现效果的一个重要…...

Linux:升级OpenSSL和OpenSSH
原因是现有版本存在安全漏洞,需要升级到新版本 原有版本和升级后的版本 OpenSSL 1.0.2k-fips 26 Jan 2017 -> OpenSSL 1.1.1w 11 Sep 2023OpenSSH_7.4p1, OpenSSL 1.0.2k-fips 26 Jan 2017 -> OpenSSH_9.5p1, OpenSSL 1.1.1w 11 Sep 2023目录 查看现有版…...

方法的入栈和出栈
一.作用域问题 1.全局作用域 在全局都能进行访问的变量 var a 10;function fn() {var b 20;return a b;}console.log(fn()); 2.局部的作用域 只能在限定的范围内进行访问 function fn() {var b 20;}console.log(b); b is not defined 打印的结果是b这个变量没用定义 3…...

PHP介绍
🐌博主主页:🐌倔强的大蜗牛🐌 📚专栏分类:PHP❤️感谢大家点赞👍收藏⭐评论✍️ 目录 一、PHP是什么? 二、 PHP 文件是什么? 三、PHP能做什么? 四、P…...

接口自动化测试之-requests模块详解
一、requests背景 Requests 继承了urllib2的所有特性。Requests支持HTTP连接保持和连接池,支持使用cookie保持会话,支持文件上传,支持自动确定响应内容的编码,支持国际化的 URL 和 POST 数据自动编码。 二、requests安装 利用p…...

低代码+定制物资管理:创新解决方案探析
引言 在当今快速变化的商业环境中,企业面临着不断增长的挑战,如提高效率、降低成本、满足客户需求等。为了应对这些挑战,企业需要不断创新并采用先进的技术解决方案。在这样的背景下,低代码开发和定制化物资管理成为了引领企业变…...

13 【PS作图】人物绘画理论-脸型
三庭五眼 三庭:脸的长度比例 (1)发际线到眉毛 (2)眉毛到鼻底 (3)鼻底到下巴 三个部分大致为三等分 五眼:脸的宽度比例 以眼睛长度为单位,把脸的宽度分成五等分&#x…...

Python批量修改图片文件名中的指定名称
批量处理图像时,图片名有时需要统一,本教程仅针对图片中名如:0001x4.png,批量将图片名中的x4去除,只留下0001.png的情况。 如果想要按照原图片顺序批量修改图片名,参考其它博文:按照原顺序批量…...

STM32点灯大师(点了一颗LED灯,轮询法)
配置操作: 一、使用CubeMX配置到大致的操作 1.1 选择芯片 1.2 选择引脚(根据电路图) 1.3 配置gpio口 1.4 配置系统 1.5文件项目操作 最后就是点击 二、点击CubeMX生成的代码,并且修改代码 2.1 看看效果 2.2 写代码...

动态规划算法:路径问题
例题一 解法(动态规划): 算法思路: 1. 状态表⽰: 对于这种「路径类」的问题,我们的状态表⽰⼀般有两种形式: i. 从 [i, j] 位置出发,巴拉巴拉; ii. 从起始位置出…...

盘一盘接口测试的那些痛点,你现在会解决了吗
前言 说到接口测试,想必大家一定不会陌生。接口测试就是测试系统组件间,接口对接是否顺畅的一种测试。包括测试数据能否交换、能否传递、能否正常控制管理过程,以及系统间的相互逻辑依赖关系,等等。 由于接口测试主要是检测系统…...

基于alpha shapes的边缘点提取(matlab)
1、原理介绍 由Edelsbrunner H提出的alpha shapes算法是一种简单、有效的快速提取边界点算法。其克服了点云边界点形状影响的缺点,可快速准确提取边界点。如下图所示,对于任意形状的平面点云,若一个半径为a的圆,绕其进行滚动&…...

C#三人飞行棋
C#三人飞行棋 #region 1控制台设置int w 50, h 30; ConsoleInit(w, h); #endregion#region 2 场景选择实例//声明一个表示场景标识的变量 E_SceneType nowSceneType new E_SceneType(); while (true) {switch (nowSceneType){case E_SceneType.Begion://开始场景逻辑Consol…...

Notes for the missing semester. Useful and basic knowledge about Linux.
The Shell Contents The first course is to introduce some simple commands. I’ll list some commands that I’m not familiar with: # --silent means dont give log info, # --head means we only want the http head. curl --head --silent bing.com.cn# cut --deli…...

【信息系统项目管理师知识点速记】资源管理基础
项目团队 执行项目工作,实现项目目标的一组人员。成员具备不同技能,可全职或兼职,随项目进展而变化。参与项目规划和决策,贡献专业技能,增强对项目的责任感。项目管理团队 直接参与项目管理活动的成员,负责项目管理和领导。负责项目各阶段的启动、规划、执行、监督、控制…...

Android性能优化面试题汇总
Android的性能优化涉及多个方面,如启动优化、稳定性优化、内存优化、网络优化、电量优化、安全优化等方面。 一、稳定性优化 1.1 你们做了哪些稳定性方面的优化 随着项目的逐渐成熟,用户基数逐渐增多,DAU持续升高,我们遇到了很多稳定性方面的问题,对于我们技术同学遇到…...

Ansible 自动化运维工具 - 了解和模块应用
目录 一. Ansible 的相关知识 1.1 Ansible 工具的简介 1.2 Ansible的四大组件 1.3 运维自动化工具 1.4 Ansible 和其它自动化运维工具对比 1.5 Ansible 的优缺点 二. Ansible 环境安装部署 2.1 管理端安装 ansible 2.2 配置主机清单 三. ansible 命令行模块 3.1 comm…...

AI神助攻!小白也能制作自动重命名工具~
我们平时从网上下载一些文件,文件名很多都是一大串字母和数字,不打开看看,根本不知道里面是什么内容。 我想能不能做个工具,把我们一个文件夹下面的所有word、excel、ppt、pdf文件重命名为文件内容的第一行。 我们有些朋友可能不会…...

(读书笔记-大模型) LLM Powered Autonomous Agents
目录 智能体系统的概念 规划组件 记忆组件 工具组件 案例研究 智能体系统的概念 在大语言模型(LLM)赋能的自主智能体系统中,LLM 充当了智能体的大脑,其三个关键组件分别如下: 首先是规划,它又分为以下…...

超分辨率重建——BSRN网络训练自己数据集并推理测试(详细图文教程)
目录 一、BSRN网络总结二、源码包准备三、环境准备3.1 报错KeyError: "No object named BSRN found in arch registry!"3.2 安装basicsr源码包3.3 参考环境 四、数据集准备五、训练5.1 配置文件参数修改5.2 启动训练5.2.1 命令方式训练5.2.2 配置Configuration方式训…...

C语言实现贪吃蛇
目录 前言一 . 游戏背景1. 背景介绍2. 项目目标3. 技术要点 二 . 效果演示三 . 游戏的设计与分析1. 核心逻辑2. 设计与分析游戏开始Gamestart()函数游戏运行Gamerun()函数游戏结束Gameend()函数 四 . 参考代码五 . 总结 前言 本文旨在使用C语言和基础数据结构链表来实现贪吃蛇…...

高可用系列四:loadbalancer 负载均衡
负载均衡可以单独使用,也常常与注册中心结合起来使用,其需要解决的问题是流量分发,这是就需要定义分发策略,当然也包括了故障切换的能力。 故障切换 故障切换是负载均衡的基本能力,和注册中心结合时比较简单…...

Ruby递归目录文件的又一种方法
经常派得上用场,记录一下。 递归文件做一些操作 #encoding:utf-8require pathnamedef recursive_enum_files(from_path)from_path Pathname.new(from_path)raise ArgumentError,must start at a directory. unless from_path.directory?from_path.enum_for(:fin…...

【爬虫】爬取A股数据写入数据库(一)
1. 对东方财富官网的分析 步骤: 通过刷新网页,点击等操作,我们发现https://datacenter-web.eastmoney.com/api/data/v1/get?请求后面带着一些参数即可以获取到相应数据。我们使用python来模拟这个请求即可。 我们以如下选择的页面为切入点…...