【数据结构与算法】之五道链表进阶面试题详解!
目录
1、链表的回文结构
2、相交链表
3、随机链表的复制
4、环形链表
5、环形链表(||)
6、完结散花
个人主页:秋风起,再归来~
数据结构与算法
个人格言:悟已往之不谏,知来者犹可追
克心守己,律己则安!
1、链表的回文结构
题目描述:
对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。
给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。
测试样例:
1->2->2->1返回:true题目链接:OJ链接
解题代码:
ListNode* findMid(ListNode* head)
{struct ListNode* fast=head,*slow=head;while(fast){fast=fast->next->next;slow=slow->next;}return slow;
}ListNode* reverse(ListNode* mid)
{ListNode* n1=NULL;ListNode* n2=mid;ListNode* n3=mid->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3){n3=n3->next;}}return n1;
}class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code her//找中间节点ListNode* mid=findMid(A);//把中间节点后的节点逆置ListNode* rmid=reverse(A);while(A){if(A->val!=rmid->val){return false;}A=A->next;rmid=rmid->next;}return true;}
};
2、相交链表
题目描述:
给你两个单链表的头节点
headA
和headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回null
。图示两个链表在节点
c1
开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
自定义评测:
评测系统 的输入如下(你设计的程序 不适用 此输入):
intersectVal
- 相交的起始节点的值。如果不存在相交节点,这一值为0
listA
- 第一个链表listB
- 第二个链表skipA
- 在listA
中(从头节点开始)跳到交叉节点的节点数skipB
- 在listB
中(从头节点开始)跳到交叉节点的节点数评测系统将根据这些输入创建链式数据结构,并将两个头节点
headA
和headB
传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。
示例 1:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出:Intersected at '8' 解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。 从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。 在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。 — 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。
示例 2:
输入:intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出:Intersected at '2' 解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。 从各自的表头开始算起,链表 A 为 [1,9,1,2,4],链表 B 为 [3,2,4]。 在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。
示例 3:
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出:null 解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。 由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。 这两个链表不相交,因此返回 null 。
提示:
listA
中节点数目为m
listB
中节点数目为n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
- 如果
listA
和listB
没有交点,intersectVal
为0
- 如果
listA
和listB
有交点,intersectVal == listA[skipA] == listB[skipB]
进阶:你能否设计一个时间复杂度
O(m + n)
、仅用O(1)
内存的解决方案?题目链接:OJ链接
解题代码:
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode *tailA=headA,*tailB=headB;int lenA=0,lenB=0;while(tailA->next){lenA++;tailA=tailA->next;}while(tailB->next){lenB++;tailB=tailB->next;}if(tailA!=tailB)return NULL;int gap=abs(lenA-lenB);//差距步//假设A为长链表struct ListNode *longList=headA,*shortList=headB;if(lenA<lenB){longList=headB;shortList=headA;}while(gap--){longList=longList->next;}while(longList){if(longList==shortList)return shortList;longList=longList->next;shortList=shortList->next;}return NULL;
}
3、随机链表的复制
题目描述:
给你一个长度为
n
的链表,每个节点包含一个额外增加的随机指针random
,该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由
n
个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的next
指针和random
指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。例如,如果原链表中有
X
和Y
两个节点,其中X.random --> Y
。那么在复制链表中对应的两个节点x
和y
,同样有x.random --> y
。返回复制链表的头节点。
用一个由
n
个节点组成的链表来表示输入/输出中的链表。每个节点用一个[val, random_index]
表示:
val
:一个表示Node.val
的整数。random_index
:随机指针指向的节点索引(范围从0
到n-1
);如果不指向任何节点,则为null
。你的代码 只 接受原链表的头节点
head
作为传入参数。示例 1:
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]示例 2:
输入:head = [[1,1],[2,1]] 输出:[[1,1],[2,1]]示例 3:
输入:head = [[3,null],[3,0],[3,null]] 输出:[[3,null],[3,0],[3,null]]提示:
0 <= n <= 1000
-104 <= Node.val <= 104
Node.random
为null
或指向链表中的节点。题目链接:OJ链接
解题代码:
struct Node* copyRandomList(struct Node* head) {struct Node* cur=head;//将复制的链表先尾插到原链表的后面while(cur){struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;copy->next=cur->next;cur->next=copy;cur=copy->next;}//复制链表的random的指向cur=head;while(cur){struct Node* copy=cur->next;if(cur->random==NULL){copy->random=NULL;}else{copy->random=cur->random->next;}cur=copy->next;}//将复制链表穿起来,并恢复原链表struct Node* copyhead=NULL,*copytail=NULL;cur=head;while(cur){struct Node* copy=cur->next;struct Node* next=copy->next;if(copyhead==NULL){copyhead=copytail=copy;}else{copytail->next=copy;copytail=copytail->next;}cur->next=next;//恢复原链表cur=next;}return copyhead;
}
4、环形链表
题目描述:
给你一个链表的头节点
head
,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪
next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos
不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ,则返回
true
。 否则,返回false
。示例 1:
输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。示例 2:
输入:head = [1,2], pos = 0 输出:true 解释:链表中有一个环,其尾部连接到第一个节点。示例 3:
输入:head = [1], pos = -1 输出:false 解释:链表中没有环。提示:
- 链表中节点的数目范围是
[0, 104]
-105 <= Node.val <= 105
pos
为-1
或者链表中的一个 有效索引 。进阶:你能用
O(1)
(即,常量)内存解决此问题吗?题目链接:OJ链接
解题代码:
bool hasCycle(struct ListNode *head) {struct ListNode* fast=head,*slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){return true;}}return false;
}
5、环形链表(||)
题目描述:
给定一个链表的头节点
head
,返回链表开始入环的第一个节点。 如果链表无环,则返回null
。如果链表中有某个节点,可以通过连续跟踪
next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。如果pos
是-1
,则在该链表中没有环。注意:pos
不作为参数进行传递,仅仅是为了标识链表的实际情况。不允许修改 链表。
示例 1:
输入:head = [3,2,0,-4], pos = 1 输出:返回索引为 1 的链表节点 解释:链表中有一个环,其尾部连接到第二个节点。示例 2:
输入:head = [1,2], pos = 0 输出:返回索引为 0 的链表节点 解释:链表中有一个环,其尾部连接到第一个节点。示例 3:
输入:head = [1], pos = -1 输出:返回 null 解释:链表中没有环。提示:
- 链表中节点的数目范围在范围
[0, 104]
内-105 <= Node.val <= 105
pos
的值为-1
或者链表中的一个有效索引进阶:你是否可以使用
O(1)
空间解决此题?题目链接:OJ链接
解题代码:
struct ListNode * hasCycle(struct ListNode *head) {struct ListNode* fast=head,*slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){return fast;}}return NULL;
}
struct ListNode *detectCycle(struct ListNode *head) {if(hasCycle(head)==NULL){return NULL;}else{struct ListNode* meet=hasCycle(head);struct ListNode* cur=head;while(cur){if(cur==meet){return cur;}cur=cur->next;meet=meet->next;}}return NULL;
}
6、完结散花
好了,这期的分享到这里就结束了~
如果这篇博客对你有帮助的话,可以用你们的小手指点一个免费的赞并收藏起来哟~
如果期待博主下期内容的话,可以点点关注,避免找不到我了呢~
我们下期不见不散~~
相关文章:

【数据结构与算法】之五道链表进阶面试题详解!
目录 1、链表的回文结构 2、相交链表 3、随机链表的复制 4、环形链表 5、环形链表(||) 6、完结散花 个人主页:秋风起,再归来~ 数据结构与算法 个人格言:悟已往之不谏,知…...

vue2实现生成二维码和复制保存图片功能(复制的同时会给图片加文字)
<template><divstyle"display: flex;justify-content: center;align-items: center;width: 100vw;height: 100vh;"><div><!-- 生成二维码按钮和输入二维码的输入框 --><input v-model"url" placeholder"输入链接" ty…...
Redis之字符串类型深入之SDS底层结构
作为一名程序员不可能不知道redis 知道redis不可能不知道redis的字符串 如果你真的熟悉redis不能不知道sds, 我们探究一下redis字符串的底层结构 sds翻译过来就是动态扩容(Simple Dynamic String)、先看一下最早版本redis的sds结构体 struct sdshdr{int len; //记录数组中…...

Cesium 3dTileset 支持 uv 和 纹理贴图
原理: 使用自定义shader实现uv自动计算 贴图效果: uv效果:...
C++可变参数模板中的省略号
看可变参数模板代码时常会遇到省略号的使用,这类奇特的“...”出现位置还不固定,容易引起困惑。C最近一直不用都快废了,在此想对省略号的使用做个简单归纳以提醒自己。可变参数模板以两种方式使用省略号。 在参数名称的左侧,表示“…...
uni-ui 使用uni-icons有些图标显示不出来,如down,up图标
问题描述 我使用的是uni创建时勾选的uni-ui模板,一次偶然机会发现down图标显示不出,left,right等其他图标又可以。 最后发现使用uni-icons不是最新版本导致的,使用模板生成的icons是1.3.5版本,我在插件市场找到的是2.0…...

动态增删表格
期望目标:实现一个能通过按钮来动态增加表格栏,每次能添加一行,每行末尾有一个删减按钮。 <el-button type"text" class"primary"click"addMember()">添加</el-button> <el-table:data"m…...

Java-(乘法表之后)增强for循环
这里我们先做个了解,之后我会在数组中进行详细介绍Java5引入了一种主要用于数组或集合的增强型for循环Java增强型for循环语法格式如下 For(声明语句:表达式){ //代码语句 } 声明语句:声明新的局部变量,该变量的类型…...

Celery(分布式任务队列)入门学习笔记
Celery 的简单介绍 用 Celery 官方的介绍:它是一个分布式任务队列; 简单,灵活,可靠的处理大量消息的分布式系统; 它专注于实时处理,并支持任务调度。 Celery 如果使用 RabbitMQ 作为消息系统的话,整个应用体系就是下…...
【网络】tcp协议如何保证可靠性
TCP(Transmission Control Protocol)是一种面向连接的、可靠的传输层协议,为网络通信提供了可靠性和连接稳定性。本文将详细介绍 TCP 协议如何保证数据的可靠传输和连接的稳定性,并分析其优缺点。 可靠性保证 序号和确认机制&…...

select,poll,epoll
在 Linux Socket 服务器短编程时,为了处理大量客户的连接请求,需要使用非阻塞I/O和复用,select,poll 和 epoll 是 Linux API 提供的I/O复用方式。 \selectpollepoll操作方式遍历遍历回调底层实现数组链表哈希表IO效率每次调用都进…...
【48天笔试强训】day18
题目1 描述 有一种兔子,从出生后第3个月起每个月都生一只兔子,小兔子长到第三个月后每个月又生一只兔子。 例子:假设一只兔子第3个月出生,那么它第5个月开始会每个月生一只兔子。 一月的时候有一只兔子,假如兔子都…...

链表经典面试题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目录 查看现有版…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...

如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
多元隐函数 偏导公式
我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式,给定一个隐函数关系: F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 🧠 目标: 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z、 …...