【初阶数据结构】——leetcode:160. 相交链表

文章目录

  • 1. 题目介绍
  • 2. 思路1:暴力求解
    • 算法思想
    • 代码实现
  • 3. 思路2:快慢指针
    • 算法思想
    • 代码实现

1. 题目介绍

链接: link
在这里插入图片描述
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

2. 思路1:暴力求解

算法思想

首先第一种思路就是暴力求解,这可能是我们最容易想到的:

让A链表的每个结点依次与B中所有结点逐个比较(拿B的跟A比也是一样),当然这里要注意比较的时候应该比较结点的地址,而不应该比较结点的值。结点的值一样并不能证明它们相交。
这种方法思想很简单,但是效率不好,这样的话时间复杂度就是O(N^2)

代码实现

代码也很简单,可以给大家写一下:

在这里插入图片描述
在这里插入图片描述
也可以通过。

//暴力求解,让A链表的每个结点依次与B中所有结点逐个比较。O(N^2)
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    while (curA)
    {
        curB=headB;
        while (curB)
        {
            if (curA == curB)
                return curA;
            curB = curB->next;
        }
        curA = curA->next;
    }
    return NULL;
}

但是上面的算法效率不是很好,我们能不能优化一下呢?

3. 思路2:快慢指针

算法思想

大家思考一个问题:

上面我们暴力比对结点的地址来寻找链表的交点。
但是为什么要拿A链表的每个结点依次与B中所有结点逐个比较呢?
为什么不能同步的遍历两个链表,比较对应的结点呢?
如果同步遍历话,就是O(N)
🆗,不能直接这样,因为两个链表的长度可能是不一样的。
比如像这样
在这里插入图片描述
如果我们同步的遍历去比对,显然是不行的,不能得到正确的结果。

那不能直接同步遍历两个链表的去比较,我们能不能想个办法让他们可以同步遍历去比较呢?

我们来分析一下。
如果两个链表相交,但是长度不相等,那么不相等的部分一定是在交点之前的。
因为相交之后它们后面的结点都是一样的嘛。
在这里插入图片描述
那上面我们分析了,就是因为两个链表的长度可能不一样,所以不能同步遍历去比较。
那我们能不能把他们变成一样长呢?
🆗,我们可以这样做
在这里插入图片描述
我们可以同步遍历去比较。
但是,如果长度不相等,我们要先让较长的那个链表的遍历指针先走长度的差值步
在这里插入图片描述
此时,我们看到,是不是就可以让curA和curB同时往后走,比较对应的结点了。
在这里插入图片描述
这样如果它们有交点的话,就一定会出现curA==curB,此时这两个指针指向的结点就是第一个交点,返回curA或curB都可。
如果没有交点,那就一直往后走curA不会和curB相等,遍历结束,curA和curB都走到空,返回curA或curB都可。(当然待会大家看我们的代码,不相交的话我们在求长度差值的时候其实就能判断出来了)

所以:

我们可以先遍历一遍两个链表,求出它们的长度,判断出谁长谁短,并计算出长度的差值。
然后让长的链表先走差值步,再同步往后走,比较对应结点,找交点。

代码实现

理清了思路,我们来写一下代码:

在这里插入图片描述
提交一下:
在这里插入图片描述
过啦!

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *curA=headA;
    struct ListNode *curB=headB;
    int lenA=0;
    int lenB=0;
    //找尾,先判断是否相交,不相交直接返回NULL,相交再找
    while(curA->next)
    {
        lenA++;
        curA=curA->next;
    }
    //计算准确长度应该这样写:while(curA)
    //这样while(curA->next)比实际长度小1,但是两个都小1,不影响差值
    //而这样写循环结束cur就是尾,可直接判断是否相交
    while(curB->next)
    {
        lenB++;
        curB=curB->next;
    }

    //尾不相等,则不相交
    if(curA!=curB)
        return NULL;
        
    //计算差值
    int gap=abs(lenA-lenB);
    //找出长的那一个
    struct ListNode *longlist=headA;
    struct ListNode *shortlist=headB;
    if(lenB>lenA)
    {
        longlist=headB;
        shortlist=headA;
    }
    //长表先走差值步
    while(gap--)
    {
        longlist=longlist->next;
    }
    //再一起走,比较两个链表的当前结点是否相同
    //,第一个相同的就是第一个交点
    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;
}

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

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

相关文章

文件批量重命名管理,一键将图片的名称进行统一重命名,高效管理文件

在数字时代,我们的生活中充满了各种文件,特别是图片文件。随着时间的推移,我们可能会遇到这样的问题:文件命名不规范,难以快速找到需要的图片。这时,一款强大的文件批量重命名管理工具就显得尤为重要。 首…

简约好用的TCPUDP小工具

csdn下载地址: https://download.csdn.net/download/a876106354/89077745

RUST语言流控制语句使用示例

1.判断语句 单条件判断: let mut x128;//声明一个32位整数x512;//修改变量原来的值为新值//如果 ... 否则//判断变量x是否大于256if x>256 {println!("x>256,x{}",x);}else {println!("x<256,x{}",x);}let is_ok:bool true;//rust中不用()if i…

前端三剑客 —— CSS (第三节)

目录 上节回顾&#xff1a; 1.CSS使用有以下几种样式; 2.选择器 1.基本选择器 2.包含选择器 3.属性选择器 [] 4.伪类选择器 &#xff1a; 5.伪元素选择器 ::before :after 3.常见样式的使用 常见样式参考表 一些特殊样式 媒体查询 自定义字体 变换效果 translate&…

2024年湖北中级职称报名时间是什么时候呢?

甘建二十年耕耘职称&#xff0c;关于职称大小事都了解 2024年湖北部分地区职称报名都已经结束了&#xff0c;恩施、十堰、黄冈、黄石、东湖高新上半年、襄阳国企事业单位和副高职称&#xff0c;这些地方的报名都截止了&#xff0c;一年一次&#xff0c;错过了有的没有第二次的话…

基于python的matplotlib库绘制折线图

代码 import matplotlib.pyplot as plt# New data for CIDEr metric beam_sizes [1, 3, 5, 7] CIDEr_new [35.2, 35.6, 38.1, 37.6]# Creating the plot for CIDEr vs Beam Size with the updated data plt.figure(figsize(10, 6)) plt.plot(beam_sizes, CIDEr_new, marker^…

pygame三角形重心坐标填充 沿x轴旋转

import pygame from pygame.locals import * import sys import math# 初始化Pygame pygame.init()# 设置窗口大小 width, height 800, 600 screen pygame.display.set_mode((width, height)) pygame.display.set_caption(3D Triangle Fill with Barycentric Coordinates)# 定…

Samba 总是需要输入网络凭证

输入网络凭证&#xff1a; 用户名是 cat /etc/samba/smb.conf&#xff0c;查看 valid users mxw 为用户名。而不是其他账号名或者用户名&#xff0c;更不是登录计算机时的计算机名&#xff1b; 密码是 需要记住安装samba服务器时&#xff0c;自己设置的password&#xff1…

鸿蒙南向开发案例:【智能养花机】

样例简介 智能养花机通过感知花卉、盆栽等植宠生长环境的温度、湿度信息&#xff0c;适时为它们补充水分。在连接网络后&#xff0c;配合数字管家应用&#xff0c;用户可远程进行浇水操作。用户还可在应用中设定日程&#xff0c;有计划的按日、按周进行浇水。在日程中用户可添…

YooAssets 使用相关

## 使用 YooAssets 动态加载原生文件时候 > 原生文件&#xff1a;txt&#xff1b;json&#xff1b;等需要直接保存文件内string字符的文件 需要将打包方式设置成为&#xff0c;PackRawFile 并且加载时候使用 API &#xff1a; YooAssets.LoadRawFileSync()YooAssets.LoadRa…

SpringBoot3入门

本文用于SpringBoot3入门。可以实现在浏览器地址栏输入localhost:8080/hello显示字符串hello world ~ 创建Maven工程 创建springboot项目。Jdk版本选17及以上&#xff0c;java选17及以上版本。打包方式选jar。因为当前工程内部已经内嵌了tomcat&#xff0c;就不用另外打包成w…

Redhat 7.9 安装dm8配置文档

Redhat 7.9 安装dm8配置文档 一 创建用户 groupadd -g 12349 dinstall useradd -u 12345 -g dinstall -m -d /home/dmdba -s /bin/bash dmdba passwd dmdba二 创建目录 mkdir /dm8 chown -R dmdba:dinstall /dm8三 配置/etc/security/limits.conf dmdba soft nproc 163…

创新视角:探索系统产品可用性测试的前沿分类方法与实践应用

一、可用性测试概念 1、什么是可用性&#xff1f; 任何与人可以发生交互的产品都应该是可用的&#xff0c;就一般产品而言&#xff0c;可用性被定义为目标用户可以轻松使用产品来实现特定目标。 ISO9241/11中的定义是&#xff1a; 一个产品可以被特定的用户在特定的场景中&a…

可视化大屏的应用(18):网络安全和信息安全领域

可视化大屏在物联网领域具有以下价值&#xff1a; 实时监控和可视化&#xff1a; 可视化大屏可以将物联网设备和传感器的数据以图表、图形和动画等形式实时展示&#xff0c;帮助用户直观地了解物联网系统的运行状态和数据趋势。通过可视化大屏&#xff0c;用户可以快速发现异…

探索--------------redis缓存三大问题及解决方案

目录 一、redis的三大缓存问题 1、缓存穿透 1.1 问题描述 1.2缓存穿透发生的条件 1.3缓存穿透发生的原因 1.4解决方案 2、缓存雪崩 2.1问题描述 2.2解决缓存雪崩问题的方法有&#xff1a; 3、缓存击穿 &#xff08;热点数据集中失效&#xff09; 3.1问题描述 3.2缓…

基于java实现的弹幕视频网站

开发语言&#xff1a;Java 框架&#xff1a;ssm 技术&#xff1a;JSP JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09; 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclip…

AMRT3D数字孪生引擎

产品概述 AMRT3D引擎是由眸瑞网络科技自主研发、拥有完全自主知识产权的一款全球首款轻量化3D图形引擎&#xff0c;引擎以核心的轻量化技术及AMRT轻量格式为支柱&#xff0c;专为数字孪生项目开发打造。 AMRT3D引擎提供一整套完善的数字孪生解决方案&#xff0c;在数据处理方…

Gemini即将收费,GPT无需注册?GPT3.5白嫖和升级教程

&#x1f310;Gemini 即将开始收费 开发者“白嫖”的好日子到头了 - Gemini将开始收费&#xff0c;影响使用Google AI for Developers提供的Gemini API的用户。 - Gemini API将引入按量付费定价&#xff0c;需要注意新的服务条款。 - 用户需在5月2日之前停止使用Gemini API和Go…

【蓝桥杯-Even Parity】

蓝桥杯-Even Parity 洛谷 UVA11464 Even Parity 暴力思路&#xff1a; 去遍历每个元素&#xff0c;如果不符合要求则翻转 时间复杂度大概在O&#xff08;2^&#xff08;nn&#xff09; nn&#xff09; 改进思路&#xff1a; 先去枚举确定第一行&#xff08;第一行得合法&…

吴恩达:AI 智能体的四种模式

一、背景 吴恩达在《What’s next for AI agentic workflows ft》分享中提出 AI 智能体的四种模式。 反思&#xff08;Reflection&#xff09;&#xff1a; LLM 检查自己的工作&#xff0c;以提出改进方法。 使用工具&#xff08;Tool use&#xff09;&#xff1a;LLM 拥有…