当前位置: 首页 > news >正文

【数据结构与算法】之五道链表进阶面试题详解!

目录

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、环形链表&#xff08;||&#xff09; 6、完结散花 个人主页&#xff1a;秋风起&#xff0c;再归来~ 数据结构与算法 个人格言&#xff1a;悟已往之不谏&#xff0c;知…...

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++可变参数模板中的省略号

看可变参数模板代码时常会遇到省略号的使用&#xff0c;这类奇特的“...”出现位置还不固定&#xff0c;容易引起困惑。C最近一直不用都快废了&#xff0c;在此想对省略号的使用做个简单归纳以提醒自己。可变参数模板以两种方式使用省略号。 在参数名称的左侧&#xff0c;表示“…...

uni-ui 使用uni-icons有些图标显示不出来,如down,up图标

问题描述 我使用的是uni创建时勾选的uni-ui模板&#xff0c;一次偶然机会发现down图标显示不出&#xff0c;left&#xff0c;right等其他图标又可以。 最后发现使用uni-icons不是最新版本导致的&#xff0c;使用模板生成的icons是1.3.5版本&#xff0c;我在插件市场找到的是2.0…...

动态增删表格

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

Java-(乘法表之后)增强for循环

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

Celery(分布式任务队列)入门学习笔记

Celery 的简单介绍 用 Celery 官方的介绍&#xff1a;它是一个分布式任务队列; 简单&#xff0c;灵活&#xff0c;可靠的处理大量消息的分布式系统; 它专注于实时处理&#xff0c;并支持任务调度。 Celery 如果使用 RabbitMQ 作为消息系统的话&#xff0c;整个应用体系就是下…...

【网络】tcp协议如何保证可靠性

TCP&#xff08;Transmission Control Protocol&#xff09;是一种面向连接的、可靠的传输层协议&#xff0c;为网络通信提供了可靠性和连接稳定性。本文将详细介绍 TCP 协议如何保证数据的可靠传输和连接的稳定性&#xff0c;并分析其优缺点。 可靠性保证 序号和确认机制&…...

select,poll,epoll

在 Linux Socket 服务器短编程时&#xff0c;为了处理大量客户的连接请求&#xff0c;需要使用非阻塞I/O和复用&#xff0c;select&#xff0c;poll 和 epoll 是 Linux API 提供的I/O复用方式。 \selectpollepoll操作方式遍历遍历回调底层实现数组链表哈希表IO效率每次调用都进…...

【48天笔试强训】day18

题目1 描述 有一种兔子&#xff0c;从出生后第3个月起每个月都生一只兔子&#xff0c;小兔子长到第三个月后每个月又生一只兔子。 例子&#xff1a;假设一只兔子第3个月出生&#xff0c;那么它第5个月开始会每个月生一只兔子。 一月的时候有一只兔子&#xff0c;假如兔子都…...

链表经典面试题01

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

基于java的CRM客户关系管理系统的设计与实现(论文 + 源码 )

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

【动态规划-最长上升子序列模型part2】:拦截导弹、导弹防御系统、最长公共上升子序列【已更新完成】

1、拦截导弹 某国为了防御敌国的导弹袭击&#xff0c;发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷&#xff1a;虽然它的第一发炮弹能够到达任意的高度&#xff0c;但是以后每一发炮弹都不能高于前一发的高度。 某天&#xff0c;雷达捕捉到敌国的导弹来袭。 由于…...

Spring 如何解决 Bean 循环依赖

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

【driver4】锁,错误码,休眠唤醒,中断,虚拟内存,tasklet

文章目录 1.互斥锁和自旋锁选择&#xff1a;自旋锁&#xff08;开销少&#xff09;的自旋时间和被锁住的代码执行时间成正比关系2.linux错误码&#xff1a;64位系统内核空间最后一页地址为0xfffffffffffff000~0xffffffffffffffff&#xff0c;这段地址是被保留的&#xff0c;如果…...

python之 函数相关知识解析

01 函数的注释与嵌套 1.函数的注释 函数的注释与普通注释的区别&#xff1a;用来说明当前函数的参数含义 param 参数名: 参数的注释信息 return: 函数的返回值 例如&#xff1a; def fun1(name):""":param name: 参数的注释信息:return: 函数的返回值"…...

监视器和显示器的区别,普通硬盘和监控硬盘的区别

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

Linux:升级OpenSSL和OpenSSH

原因是现有版本存在安全漏洞&#xff0c;需要升级到新版本 原有版本和升级后的版本 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面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 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求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

多元隐函数 偏导公式

我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式&#xff0c;给定一个隐函数关系&#xff1a; F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 &#x1f9e0; 目标&#xff1a; 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z​、 …...