链表题(4)

本章内容

正文开始前给大家推荐个网站,前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。
今天继续给大家带来链表的相关练习题。

相交链表

这道题来自力扣网,链接给大家奉上:

https://leetcode.cn/problems/intersection-of-two-linked-lists/submissions/483011644/

题目描述:
给你两个单链表的头节点 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]

思路:
首先,我们需要确认两个链表是否相交,这个比较简单,我们遍历两个链表到最后一个节点,看两个节点是否相等即可,如果相等,就代表这两个链表相交,不相等就代表两个链表不相交。这就是第一步的思路。

之后就很好想了,我们算出两个链表的长度,得到相对差值k,让长的先走k步,之后两个链表一起走,相等的时候就代表到了相交节点。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* ListA=headA;
    struct ListNode* ListB=headB;
    int lenA=1;
    int lenB=1;
    while(ListA->next!=NULL)//A链表遍历至最后
    {
        lenA++;
        ListA=ListA->next;
    }
    while(ListB->next!=NULL)//B链表遍历至最后
    {
        lenB++;
        ListB=ListB->next;
    }
    if(ListA!=ListB)//如果两个链表最后节点不相等代表不相交则返回空指针。
    {
        return NULL;
    }
    int n=abs(lenA-lenB);//设n为相对差值
    struct ListNode* longlist=headA;//假设A为长链表,B为短链表
    struct ListNode* shortlist=headB;
    if(lenA<lenB)//若假设错误,则B为长链表,A为短链表
    {
        longlist=headB;
        shortlist=headA;
    }
    while(n--)//长链表先走n步
    {
        longlist=longlist->next;
    }
    while(longlist!=shortlist)//长锻链表一起走,相等时停止
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;//返回此时的节点,即为相交节点。
}

在这里我们并不知道哪个链表长哪个链表短,所以我们假设A链表长,如果假设错误,那么将长链表换位B链表即可,之后再进行走n步操作,再长短链表一起走即可找到相交节点了。(若还有不理解地方请具体看代码注释。)

环形链表I

本题依然取自力扣网,题目链接奉上:

https://leetcode.cn/problems/linked-list-cycle/description/

给你一个链表的头节点 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 或者链表中的一个 有效索引 。

思路:
这道题思路十分明确,仅判断链表是否有环即可,所以我们用快慢指针来遍历就好,如果快指针等于空指针了,说明该链表不带环,返回空指针即可,若快慢指针遍历至相等的时候,则说明该链表带环。

bool hasCycle(struct ListNode *head) {
    struct ListNode* fast=head;
    struct ListNode* slow=head;
    while(fast&&fast->next)//快指针遍历
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)//若碰到快慢指针相等时,则说明一定是环形链表,因为慢指针等于快指针时,快指针一定遍历一遍了。
        {
            return true;
        }
    }
    return false;//快指针一定比慢指针先遍历完成,若返回false,则说明快指针或者快指针的next为空指针
}

思路十分简单,代码也十分简单,注释也给大家奉上了。

今天的分享就到此为止,谢谢大家。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

央企太卷.....来自央企的7个面试题,一个一个生产难题

说在前面 在40岁老架构师尼恩的&#xff08;50&#xff09;读者社群中&#xff0c;最近小伙伴&#xff0c;面试央企、美团、京东、阿里、 百度、头条等大厂。 下面是一个小伙伴成功拿到通过了一个央企设计研究院一面面试&#xff0c;现在把面试真题和参考答案收入咱们的宝典。…

FDM(傅里叶分解)

代码的使用教程 傅里叶分解&#xff08;FDM&#xff09; 代码原理 FDM (Frequency Division Multiplexing)是一种调制技术&#xff0c;将信号分成多个不同的频带进行传输&#xff0c;从而实现多路复用的通信方式。FDM分解原理是将不同频率的信号分解成不同的频带&#xff08;子…

网工内推 | Linux运维,六险二金,最高30K,IE认证优先

01 上海域起 招聘岗位&#xff1a;Linux运维工程师 职责描述&#xff1a; 1.负责游戏产品运维相关的工作&#xff0c;流程文档、技术文档、功能脚本的编写整理 2.负责分析并排除系统、数据库、网络、应用等游戏产品运维中出现的故障及错误 3.负责对游戏产品项目进行线上部署、…

阿里AoneFlow分支管理

分支模式 1.TrunkBased模式 工作方式 TrunkBased 模式是持续集成思想所崇尚的工作方式&#xff0c;它由单个主干分支和许多发布分支组成&#xff0c;每个发布分支在特定版本的提交点上从主干创建出来&#xff0c;用来进行上线部署和 Hotfix&#xff08;补丁&#xff09;。 …

制作Go程序的Docker容器

今天突然遇到需要将 Go 程序制作成 Docker 的需求&#xff0c;所以进行了一些研究。方法很简单&#xff0c;但是官方文档和教程有些需要注意的地方&#xff0c;所以写本文进行记录。 源程序 首先介绍一下示例程序&#xff0c;示例程序是一个 HTTP 服务器&#xff0c;会显示si…

一次java系统调优 从150到最高1800的过程

前言 在做公司系统压力测试(500个线程并发)的时候 某个服务的接口 压测初始结果如下 初始指标(最高)&#xff1a; 吞吐量 150/s TPS: 240 CPU,内存&#xff0c;带宽&#xff0c;磁盘io 如下图所示 可以看到资源使用是有问题的 cpu和带宽并没有给足压力 说明并不是资源所导致…

代码随想录算法训练营第三十九天【动态规划part02】 | 62.不同路径、63. 不同路径 II

62.不同路径 题目链接&#xff1a; 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 求解思路&#xff1a; 动规五部曲 确定dp数组及其下标含义&#xff1a;dp[i][j] 表示从&#xff08;0,0&#xff09;出发&#xff0c;到&#xff08;i,j&#x…

计算机科学速成课

建议看看计算机科学速成课&#xff0c;一门很全面的计算机原理入门课程&#xff0c;短短10分钟可以把大学老师十几节课讲的东西讲清楚&#xff01;整个系列一共41个视频&#xff0c;B站上有中文字幕版。 每个视频都是一个特定的主题&#xff0c;例如软件工程、人工智能、操作系…

Django的可重用HTML模板示例

01-配置并运行Django项目 首先按照博文 https://blog.csdn.net/wenhao_ir/article/details/131166889配置并运行Django项目。 02-创建可重用模板文件 templates目录下新建目录common&#xff0c;然后在目录common下新建文件&#xff1a;navbar.html&#xff0c;并写入下面的…

Pandas 求平均值

Pandas是Python中最流行的数据分析库之一&#xff0c;它提供了许多强大的工具来处理和分析数据集。其中&#xff0c;求平均值是数据分析中最常见的操作之一。在本文中&#xff0c;我们将从多个角度分析Pandas中如何求平均值。 一、基础操作 Pandas中求平均值的基础操作是使用m…

电磁场与电磁波part3--静态电磁场及其边值问题的解

1、当场源&#xff08;电荷、电流&#xff09;不随时间变化时&#xff0c;所产生的电场、磁场也不随时间变化&#xff0c;称为静态电磁场。静止电荷产生的静电场、在导电媒质中恒定运动电荷形成的恒定电场以及恒定电流产生的恒定磁场都属于静态电磁场。 2、静电场基本方程微分形…

深信服AC应用控制技术

拓扑图 目录 拓扑图 一.上班时间不允许使用qq(假设上班时间是上午9到12&#xff0c;下午14到18) 1.新增上班时间不允许使用qq访问权限策略 2.将策略应用到组&#xff0c;例如修仙部 3.验证 上班时间发现登录不了 下班时间可以登录 二.上班时间不允许访问视频网站(假设上班时…

springboot323基于Java的美妆购物网站的设计与实现

交流学习&#xff1a; 更多项目&#xff1a; 全网最全的Java成品项目列表 https://docs.qq.com/doc/DUXdsVlhIdVlsemdX 演示 项目功能演示&#xff1a; ————————————————

梦想编织者——Adobe Dreamweaver

今天&#xff0c;我们来谈谈一款在Adobe系列中推出的一款Adobe Dreamweaver&#xff0c;简称“DW”&#xff0c;中文名称 “梦想编织者”&#xff0c;是集网页制作和管理网站于一身的所见即所得网页代码编辑器。 利用对 HTML、CSS、JavaScript等内容的支持&#xff0c;设计人员…

java并发编程JUC:一、专栏配置+进程与线程+并行和并发+同步和异步+线程的创建、调用、查看、运行原理和相关API

专栏配置 pom.xml <properties><maven.compiler.source>1.8</maven.compiler.source><maven.compiler.target>1.8</maven.compiler.target> </properties> <dependencies><dependency><groupId>org.projectlombok<…

(论文阅读46-50)图像描述2

46.文献阅读笔记 简介 题目 Learning a Recurrent Visual Representation for Image Caption Generation 作者 Xinlei Chen, C. Lawrence Zitnick, arXiv:1411.5654. 原文链接 http://www.cs.cmu.edu/~xinleic/papers/cvpr15_rnn.pdf 关键词 2014年rnn图像特征和文本特…

目录自动清洗

文章目录 前言一、需求分析二、操作步骤详解&#xff08;标准章节&#xff09;1. 提取文章目录2. 更改保存目录.txt3. 二级标题前面加4个空格4. 在章字和节字后面添加一个空格5. 在页码前面加上>符号6. 代码完全体 三、进阶一&#xff08;有章无节小数二级标题&#xff09;1…

git基础命令

git简介 什么是git&#xff1f; git是一种分布式版本控制系统。 git与svn之间的区别是什么&#xff1f; svn是集中式版本控制系统。git是分布式版本控制系统。 什么是集中式版本控制系统&#xff1f;有哪些特点&#xff1f; 版本库是集中存放在中央服务器。集中式版本控制…

kk模组的具体应用场合

KK模组是一种高精度、高刚度的直线模组&#xff0c;广泛应用于各种自动化设备和精密仪器中。以下是KK模组的一些具体应用场合&#xff1a; 1、半导体设备&#xff1a;半导体制造过程中需要使用精密的定位和运动控制设备&#xff0c;KK模组作为一种高精度、高刚度的直线模组&…