C语言每日一题(31)相交链表

力扣160.相交链表

题目描述

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

图示两个链表在节点 c1 开始相交

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构 。

思路分析

首先明确题目所要求的:

1.两链表是否相交?

2.如果相交的话,交点在哪?

首先解决第一个问题,判断是否相交。首先两个链表的头结点可能一样也可能不一样,但如果相交的话,它们的尾结点一定是同一个,那么我们可以分别遍历这两个链表到尾,如果一样的话就代表它们一定相交,否则直接返回false。

到第二个问题,找交点,如果俩链表同时从头遍历,再找它们相同的结点的话,那么当俩链表长度不同,指针就会错位,这是不靠谱的做法,正确的做法是,将它们遍历的起点进行统一后再进行遍历,直到碰到相同的结点,就是它们的交点。

如何统一起点呢?

首先找出较长链表,将俩链表长度的差当作步数,让长链表的指针先走完这些步数,这样两个链表的指针就统一了,之后两个指针再一起遍历,直到碰到相同结点停止,返回任意一个指针即是对应的交点。

完整代码

/**
 * 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=1,lenB=1;//从1开始。
    while(curA)
    {
        lenA++;
        curA=curA->next;
    }
    while(curB)
    {
        lenB++;
        curB=curB->next;
    }
    if(curA!=curB)/判断是否相交
    {
        return NULL;
    }
    int n=abs(lenA-lenB);
    struct ListNode* longlist=headA,*shortlist=headB;//可以先假设其中一个为长链表。
    if(lenB>lenA)//如果不是在交换即可。
    {
        longlist=headB;
        shortlist=headA;
    }
    while(n--)//长指针先走
    {
        longlist=longlist->next;
    }
    while(shortlist!=longlist)//两个一起走,直到相同停下
    {
        shortlist=shortlist->next;
        longlist=longlist->next;
    }
    return longlist;//返回其中任意一个即可。
}

实现细节

注意比较的是该节点而非该节点的值,因为链表是乱序且无规律的。 

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

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

相关文章

主办方:上海视频媒体,多样式多渠道跨屏传播

传媒如春雨,润物细无声,大家好,我是51媒体网胡老师。 一,邀请视频媒体参加活动发布会,好处多多,首先现场气氛会很热烈,主办方会很有面子,视频媒体不管是电视台还是视频网站&#xf…

【自留地】前端 - uniapp - Vue - React - Flutter

uniapp uniapp自用速查表 - 我的常用组件 uniapp自用速查表 - 我的常用组件_uniapp static/customicons.css-CSDN博客文章浏览阅读1.8k次。uniapp项目登录退出、全局变量与状态、本地存储、Tabbar标签栏、顶部导航栏、下拉刷新、触底刷新、Ajax交互、内置组件样式修改、自定义…

聚观早报 |联想集团Q2财季业绩;小鹏汽车Q3营收

【聚观365】11月17日消息 联想集团Q2财季业绩 小鹏汽车Q3营收 微软发布两款自研AI芯片 FAA批准SpaceX再次发射星际飞船 2023 OPPO开发者大会 联想集团Q2财季业绩 全球数字经济领导企业联想集团公布截至2023年9月30日的2023/24财年第二财季业绩:整体营收达到10…

C++基础从0到1入门编程(一)

系统学习C 方便自己日后复习,错误的地方希望积极指正 参考视频:黑马程序员匠心之作|C教程从0到1入门编程,学习编程不再难 1 第一个C程序-HelloWorld 编写一个C程序分为四个步骤: (1)创建项目 (2&#xff…

深度学习入门(第四天)——递归神经网络与词向量原理解读

一、RNN网络架构解读 常规神经网络并不能考虑时间序列的特征(比如前天昨天今天或者带有前后关联的特征),现在每个特征都是独立考虑的,那么如果有这样的特征,网络应该怎么学呢 而递归递归网络hidden这里的转回箭头&…

全球地表水数据集JRC Global Surface Water Mapping Layers, v1.2数据

简介: 全球地表水覆盖(Global Surface Water)是利用1984至2019年获取的landsat5、landsat7和landsat8的卫星影像,生成分辨率为30米的一套全球地表水覆盖的地图集。用户可以在全球尺度上按地区回溯某个时间上地表水分的变化情况。…

MySQL内部组件与日志详解

MySQL的内部组件结构 MySQL 可以分为 Server 层和存储引擎层两部分。 Server 层主要包括连接器、查询缓存、分析器、优化器、执行器等,涵盖 MySQL 的大多数核心服务功能,以及所有的内置函数(如日期、时间、数学和加密函数等)&am…

Android开发APP显示头部Bar

Android开发显示头部Bar 需求&#xff1a; 显示如下图&#xff1a; 显示头部Bar&#xff0c;颜色也能自定义。 解决方案 这个修改是在如下三个文件里进行修改&#xff1a; 按顺序修改&#xff1a; themes.xml(night): <resources xmlns:tools"http://schemas.andr…

21 - 深入JVM即时编译器JIT,优化Java编译

说到编译&#xff0c;我猜你一定会想到 .java 文件被编译成 .class 文件的过程&#xff0c;这个编译我们一般称为前端编译。Java 的编译和运行过程非常复杂&#xff0c;除了前端编译&#xff0c;还有运行时编译。由于机器无法直接运行 Java 生成的字节码&#xff0c;所以在运行…

Odoo 15开发手册第六章 模型 - 结构化应用数据

本章我们更进一步学习模型层&#xff0c;以及如何使用模型来设计支撑应用的数据结构。我们会探讨可用的模型类型&#xff0c;以及在使用这些类型时如何定义强制进行数据验证的约束。 模型由支持不同数据类型的数据字段组成&#xff0c;一些字段类型支持定义模型间的关联。对于…

excel导入 Easy Excel

依旧是框架感觉有东西&#xff0c;但是确实是模拟不出来&#xff0c;各种零零散散的件太多了 controller层 ApiOperation(value "导入Excel", notes "导入Excel", httpMethod "POST", response ExcelResponseDTO.class)ApiImplicitParams({…

回调方法Callbak方法的理解——Java中回调的实现方式 从系统调用角度理解回调

目录 回调方法实现用反射实现直接调用callback进化&#xff1a;接口实现分离 匿名内部类 到 函数式编程 从系统调用角度理解回调同步调用异步调用不需要对方结果需要对方的结果 菜鸡问大佬问题案例同步回调异步回调基于Future的半同步 回调方法就是一个参数,将一个A方法作为参数…

Power Automate-创建自定义连接器

点击左侧导航栏&#xff0c;更多&#xff0c;点击全部发现 点击下方的自定义连接器 点击从空白创建 注意命名要用英文 常规信息中可以上传连接器icon、写一些说明 方案是观察接口地址前面的文本&#xff0c;主机是下方接口地址中蓝色框中的内容 点击下一步&#xff0c;根据API自…

CTF-PWN-堆-【前置知识】

CTF-PWN-堆 堆申请堆块main_areanabrk&sbrk函数mallocfreefree后top chunk 堆 由malloc alloc realloc 函数分配 chunk的前指的是地址低的&#xff0c;chunk的高指的是地址高的 申请堆块 ptmalloc2堆管理器&#xff1a; 通俗的讲就是相当于一个”中间商”&#xff0c;在…

Python编程技巧 – 使用列表(list)

Python编程技巧 – 使用列表(list) Python Programming Skills – Using a List 在Python编程语言中&#xff0c;我们会用到许多列表&#xff08;List&#xff09;。 一门强大的编程语言会包含列表&#xff08;或者数组&#xff09;的数据结构。列表&#xff08;或数组&#…

cpolar+LightPicture,将个人电脑改造成公网图床服务器

文章目录 1.前言2. Lightpicture网站搭建2.1. Lightpicture下载和安装2.2. Lightpicture网页测试2.3.cpolar的安装和注册 3.本地网页发布3.1.Cpolar云端设置3.2.Cpolar本地设置 4.公网访问测试5.结语 1.前言 现在的手机越来越先进&#xff0c;功能也越来越多&#xff0c;而手机…

C++ Qt 学习(九):模型视图代理

1. Qt 模型视图代理 Qt 模型视图代理&#xff0c;也可以称为 MVD 模式 模型(model)、视图(view)、代理(delegate)主要用来显示编辑数据 1.1 模型 模型 (Model) 是视图与原始数据之间的接口 原始数据可以是&#xff1a;数据库的一个数据表、内存中的一个 StringList&#xff…

什么是持续集成的自动化测试?

持续集成的自动化测试 如今互联网软件的开发、测试和发布&#xff0c;已经形成了一套非常标准的流程&#xff0c;最重要的组成部分就是持续集成&#xff08;Continuous integration&#xff0c;简称CI&#xff0c;目前主要的持续集成系统是Jenkins&#xff09;。 那么什么是持…

Python爬虫教程:从入门到实战

更多Python学习内容&#xff1a;ipengtao.com 大家好&#xff0c;我是涛哥&#xff0c;今天为大家分享 Python爬虫教程&#xff1a;从入门到实战&#xff0c;文章3800字&#xff0c;阅读大约15分钟&#xff0c;大家enjoy~~ 网络上的信息浩如烟海&#xff0c;而爬虫&#xff08;…

4G工业路由器智慧电梯联网应用方案

随着电梯老旧增多及日常管理上缺失&#xff0c;电梯安全运行上存在一定的问题&#xff0c;从全国电梯统计数据中可以发现&#xff0c;主要的电梯困人、故障事件发生在住宅小区&#xff0c;当前&#xff0c;住宅小区的电梯绝大多数是通过物业公司负责管理&#xff0c;物业公司安…