160.相交链表

·题目描述

·解题思路

————看评论区大神的思路————

设「第一个公共节点」为 node ,「链表 headA」的节点数量为 aaa ,「链表 headB」的节点数量为 bbb ,「两链表的公共尾部」的节点数量为 ccc ,则有:

头节点 headA 到 node 前,共有 a−c个节点;
头节点 headB 到 node 前,共有 b−c 个节点;


考虑构建两个节点指针 A​ , B 分别指向两链表头节点 headA , headB ,做如下操作:

指针 A 先遍历完链表 headA ,再开始遍历链表 headB ,当走到 node 时,共走步数为:
a+(b−c)
指针 B 先遍历完链表 headB ,再开始遍历链表 headA ,当走到 node 时,共走步数为:
b+(a−c)
如下式所示,此时指针 A , B 重合,并有两种情况:

a+(b−c)=b+(a−c)
若两链表 有 公共尾部 (即 c>0c > 0c>0 ) :指针 A , B 同时指向「第一个公共节点」node 。
若两链表 无 公共尾部 (即 c=0c = 0c=0 ) :指针 A , B 同时指向 nullnullnull 。
因此返回 A 即可。

·代码

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def getIntersectionNode(self,headA: ListNode, headB: ListNode ) -> ListNode:
        point_A = headA
        point_B = headB

        while point_A != point_B:

            if point_A :
                point_A = point_A.next
            else:
                point_A = headB

            if point_B:
                point_B = point_B.next
            else:
                point_B = headA

        return point_A

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

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

相关文章

CSS设置字体样式

目录 前言: 1.font-family: 2.font-style: 3.font-weight: 4.font-size: 5.font-variant: 6.font: 前言: 在网页中字体是重要的组成部分,使用好字体可以让网页更…

第一次在msf控制台中运行search命令提示Module database cache not built yet问题解决

0x00 问题描述 在新装的kali虚拟机中使用msfconsole执行search命令时提示Module database cache not built yet问题,显然,是我们相关的数据库缓存存在问题。 故障现象: 0x01 启动数据库服务 msf中的search功能是基于postgresql来实现的&am…

python学习25:python中的元组(tuple)

python中的元组(tuple) 1.什么是元组? 元组也是容器数据类型的一种,同列表几乎是一样的,都是可以在里面封装多个,不同类型的元素在内;与列表最大的不同就是: 元组一旦被定义,就不能修改 2.元组…

物理层习题及其相关知识(谁看谁不迷糊呢)

1. 对于带宽为50k Hz的信道,若有4种不同的物理状态来表示数据,信噪比为20dB 。(1) 按奈奎斯特定理,信道的最大传输数据速率是多少?(2) 按香农定理,信道的最大传输数据速度…

Java设计模式—享元(FlyWeight)模式

享元模式(Flyweight),运用共享技术有效地支持大量细粒度的对象 public abstract class Piece {protected PieceColor m_color;protected PiecePos m_pos;public Piece(PieceColor color ,PiecePos pos){m_color color;m_pos pos;}public ab…

Java笔试总结

. 操作系统中关于竞争和死锁的关系下面描述正确的是? A 竞争一定会导致死锁 B 死锁一定由竞争引起 C 竞争可能引起死锁 D 预防死锁可以防止竞争 答案: C 进程的控制信息和描述信息存放在()。 A JCB B PCB C AFT D SFT 答案: B 当系统发生抖动(thrash…

元宇宙虚拟空间的场景的渲染(五)

前言 该文章主要讲元宇宙虚拟空间的场景的渲染,基本核心技术点,不多说,直接引入正题。 场景的渲染 下面第二个图中的代码是一个循环渲染逻辑,首先getDelta 获取2次时间的时间间隔,requestAnimationFrame请求我们的一…

Qt Creator 界面

🐌博主主页:🐌​倔强的大蜗牛🐌​ 📚专栏分类:QT❤️感谢大家点赞👍收藏⭐评论✍️ 目录 一、认识 Qt Creator 界面 1、总览 2、左边栏 3、代码编辑区 4、UI设计界面 5、构建区 一、认识 …

99%的人不知道,Oracle resetlogs强制开库需要推进SCN?

📢📢📢📣📣📣 哈喽!大家好,我是【IT邦德】,江湖人称jeames007,10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】!😜&am…

算法---分治(归并排序)

T04BF &#x1f44b;专栏: 算法|JAVA|MySQL|C语言 &#x1faf5; 小比特 大梦想 此篇文章与大家分享分治算法关于归并排序的专题 对于归并排序在我个人主页专栏 <排序> 有详细的介绍 如果有不足的或者错误的请您指出! 1.归并排序 题目: 排序数组 1.1解析 关于归并排序…

STM32使用HAL库获取GPS模块HT1818Z3G5L信息(方法1)

1、写在最前 先了解一下GPRMC的格式 格 式&#xff1a; GPRMC,024813.640,A,3158.4608,N,11848.3737,E,10.05,324.27,150706,A*50 说 明&#xff1a; 字段 0&#xff1a;$GPRMC&#xff0c;语句ID&#xff0c;表明该语句为Recommended Minimum Specific GPS/TRANSIT Data&…

Open CASCADE学习|在给定的TopoDS_Shape中查找与特定顶点 V 对应的TopoDS_Edge编号

enum TopAbs_ShapeEnum{TopAbs_COMPOUND,TopAbs_COMPSOLID,TopAbs_SOLID,TopAbs_SHELL,TopAbs_FACE,TopAbs_WIRE,TopAbs_EDGE,TopAbs_VERTEX,TopAbs_SHAPE}; 这段代码定义了一个名为 TopAbs_ShapeEnum 的枚举类型&#xff0c;它包含了表示不同几何形状类型的常量。这些常量通常…

通过学习mayfly-go,我学会了前端如何优雅设计字典值

shigen坚持更新文章的博客写手&#xff0c;擅长Java、python、vue、shell等编程语言和各种应用程序、脚本的开发。记录成长&#xff0c;分享认知&#xff0c;留住感动。 个人IP&#xff1a;shigen shigen在假期的最后一天早晨起来&#xff0c;翻看了一下博客&#xff0c;一个ma…

spring注解驱动系列--声明式事务

一、环境搭建 一、导入依赖 <!-- 数据源、数据库驱动、spring-jdbc模块--> <dependency> <groupId>org.springframework</groupId> <artifactId>spring-jdbc</artifactId> <version>4.3.12.RE…

Dockerfile详解构建镜像

Dockerfile构建企业级镜像 在服务器上可以通过源码或rpm方式部署Nginx服务&#xff0c;但不利于大规模的部署。为提高效率&#xff0c;可以通过Dockerfile的方式将Nginx服务封装到镜像中&#xff0c;然后Docker基于镜像快速启动容器&#xff0c;实现服务的快速部署。 Dockerf…

统一网关 Gateway(黑马程序员)

网关的技术实现 在 SpringCloud 中网关的实现包括两种&#xff1a; gatewayzuul Zuul 是基于 Servlet 的实现&#xff0c;属于阻塞式编程。而 SpringCloudGateway 则是基于 Spring5 中提供的 WebFlux &#xff0c; 属于响应式编程的实现&#xff0c;具备更好的性能。 网关的作…

火柴排队(c++实现)

题目 涵涵有两盒火柴&#xff0c;每盒装有 n 根火柴&#xff0c;每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列&#xff0c;同一列火柴的高度互不相同&#xff0c;两列火柴之间的距离定义为&#xff1a; 其中 ai 表示第一列火柴中第 i 个火柴的高度&#xf…

【OneAPI】贴纸生成API

OneAPI新接口发布&#xff1a;贴纸生成 生成一个10241024像素的贴纸。 API地址&#xff1a;POST https://oneapi.coderbox.cn/openapi/api/stickers 请求参数&#xff08;body&#xff09; 参数名类型必填含义说明prompt提示词是提示词示例&#xff1a;一只可爱的小狗 响应…

网络网络层之(1)IPv4地址

网络网络层之(1)IPv4地址 Author: Once Day Date: 2024年4月1日 一位热衷于Linux学习和开发的菜鸟&#xff0c;试图谱写一场冒险之旅&#xff0c;也许终点只是一场白日梦… 漫漫长路&#xff0c;有人对你微笑过嘛… 全系列文档可参考专栏&#xff1a;通信网络技术_Once-Day的…

嵌入式系统初学者指南

什么是嵌入式系统&#xff1f; 嵌入式系统是一种独立的、基于微处理器的计算机系统。您可以将其视为大型系统的一部分的微型计算机。如今&#xff0c;从洗碗机到波音 747&#xff0c;几乎所有“电子”产品内部都有嵌入式系统。但是&#xff0c;嵌入式系统与笔记本电脑或手机不…