【LeetCode链表#12】链表相交

链表相交

同:160.链表相交

力扣题目链接(opens new window)

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

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

img

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

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

示例 1:

img

示例 2:

img

示例 3:

imgimg

思路

根据LeetCode题目下的隐藏提示4以及观察可知:

如果两个链表存在相交部分,那么自相交点之后的节点应该都是重合的(下面的图没体现出来)

由此,我们可以将待判断的两个链表的尾部对齐

将较长链表的当前指针指向与短链表的对齐

面试题02.07.链表相交_2

从此处同时向后遍历,直到找到相同的节点

思路大概是这样的,那么关键要解决两个问题:

​ 1、如何找出较长的那个链表?

​ 2、如何尾部对齐?

因为我们有两个链表,那么先直接定义两个指针curA和curB,并且,curA一定是指向较长的那个链表的指针。

实际上第一个问题用遍历解决就行了,但是在过程中,万一最开始定义的链表并不是最长的,应该如何处理?例如curA实际上比curB短,这时需要将两者调换

调换过程也比较简单粗暴,当记录长度的变量显示curA比curB短后,将curA和curB交换就行(同时还要将长度变量互换)

这个时候,求出两链表的长度差,将curA移动到curB所在的位置,就能将尾部对齐

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //初始化两链表的头节点,默认A为较长的那个
        ListNode curA = headA;
        ListNode curB = headB;

        //用于记录链表长度
        int lenA = 0;
        int lenB = 0;

        //分别遍历获取两链表长度
        while(curA != null){
            lenA++;
            curA = curA.next;
        }

        while(curB != null){
            lenB++;
            curB = curB.next;
        }

        //遍历结束重新将指针放回头节点
        curA = headA;
        curB = headB;


        //如果lenB大,就要交换一下
        if(lenB > lenA){
            //交换节点
            ListNode tempN;
            tempN = curA;
            curA = curB;
            curB = tempN;

            //交换长度信息
            int tempL = lenA;
            lenA = lenB;
            lenB = tempL;
        }

        //尾部对齐
        //先计算长度差值
        int subResult = lenA - lenB;
        //移动指针对齐短链表
        while(subResult-- > 0){
            curA = curA.next;
        }

        //两链表同时向后遍历,遇到相同值便返回
        while(curA != null){
            if(curA == curB){
                return curB;//A、B都行
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;   
    }
}
易错点

1、统计完长度记得把指针调回链表头部

本文转载于网络 如有侵权请联系删除

相关文章

  • CompletableFuture使用详解

    大家好,又见面了,我是你们的朋友全栈君。一、简介1.1概述在上一篇文章《CompletionService使用与源码分析》中,已经介绍过了Future的局限性,它没法直接对多个任务进行链式、组合等处理,需要借助并发工具类才能完成,实现逻辑比较复杂。而CompletableFuture是对Future的扩展和增强。CompletableFuture实现了Future接口,并在此基础上进行了丰富的扩展,完美弥补了Future的局限性,同时CompletableFuture实现了对任务编排的能力。借助这项能力,可以轻松地组织不同任务的运行顺序、规则以及方式。从某种程度上说,这项能力是它的核心能力。而在以往,虽然通过CountDownLatch等工具类也可以实现任务的编排,但需要复杂的逻辑处理,不仅耗费精力且难以维护。CompletableFuture的继承结构如下: CompletionStage接口定义了任务编排的方法,执行某一阶段,可以向下执行后续阶段。异步执行的,默认线程池是ForkJoinPool.commonPool(),但为了业务之间互不影响,且便于定位问题,强烈推荐使用自定义线

  • golang pprof label 使用

    tracevspprofgotooltrace和gotoolpprof两个工具的使用方法类似,但是两者的原理和侧重点不同:1,gotooltrace更侧重于记录分析采样时间内运行时系统具体干了什么。原理是监听golang调度器的事件,记录操作耗时等相关信息。Tracer为每个event打的时间戳都精确到纳秒(nanosecond)级精度。性能损耗大。与goroutine调度有关的事件信息:goroutine的创建、启动和结束;goroutine在同步原语(包括mutex、channel收发操作)上的阻塞与解锁。与网络有关的事件:goroutine在网络I/O上的阻塞和解锁;与系统调用有关的事件:goroutine进入系统调用与从系统调用返回;与垃圾回收器有关的事件:GC的开始/停止,并发标记、清扫的开始/停止。2,gotoolpprof便是一个基于采样(sampling)的性能剖析(profiing)辅助工具。它基于定时器对运行的go程序进行各种采样,包括诸如CPU时间、内存分配等方面。在Go运行时内部,CPU分析使用操作系统计时器来定期(每秒约100次,即10ms一次)中断执行。在每

  • ISP(图像信号处理)介绍

    ISP图像信号处理 1,ISP图像信号处理介绍2,ISP的目的是什么?3,ISP的处理流程以及算法3.1镜头的几何变形3.2镜头渐晕3.3曝光控制:曝光不足3.4OpticalBlackClamping3.5ImageCompression4ISP的内部组成5,ICISP架构5.1NuCORESip1270DBE5.2TITMS320DM2705.3DM270CCD1,ISP图像信号处理介绍ISP(ImageSignalProcessing)图像信号处理。主要用来对前端图像传感器输出信号处理的单元,以匹配不同厂商的图象传感器。相机用图像处理器ISP(ImageSignalProcessor)。被管道化的图像处理专用引擎可以高速处理图像信号。也搭载了为了实现AutoExposure/AutoFocus/AutoWhiteBalance评测的专用电路。另外,THine开发的减噪等图像处理模块,能令各个CMOS传感器实现最高画质。 2,ISP的目的是什么?像素对某些波长组之间的光很敏感,本质上它们是颜色不可知的。获取彩色图像的方法是在顶部放置一个滤镜(通常是拜耳图案滤色镜),然后对相邻像素的

  • 「译」 .NET 5 新增的Http, Sockets, DNS 和 TLS 遥测

    .NET一直在稳定的增加和改善对应用程序进行跨平台的诊断分析,在.NETCore3.0,我们看到了EventCounters[1]的介绍,用于观察和分析指标测量。我最近在几个.NETCore的应用程序中使用counters,来跟踪服务一段时间内http的请求数量。.NET5一直在进步,我一直在关注runtimerepository[2]的动态和工作,在http发生外部调用时,添加了新的遥测计数器和一些核心组件的事件,包括HttpClient,Sockets,DNS和Security。在这篇文章中,我将展示如何在runtime(运行时)消费这些信息,需要注意的是,本文的代码仅仅是简单的实现,如果在生产中使用话,你还需要考虑到性能开销或者其他。定义EventListener.NET中已经有了EventListener抽象类,我们可以在代码中继承这个类,来自定义一个listenerinternalsealedclassTelemetryListener:EventListener { ... }复制接下来,我们重写OnEventSourceCreated方法,来处理下边的几种特定事件的消息p

  • 原生小程序之工程化探索

    前言习惯用webpack对项目开发工程化,接触小程序后,稍微有点不适应,市面上有taro等优秀的小程序框架可以使用,由于负责项目历史背景,而无法大规模改造,因此只能做一些简单的工程化方案规范代码配置eslintvscode安装插件eslint配置husky,利用gitcommit钩子进行eslint检查,检测不通过不能提交代码1.package.json"lint-staged":{ "**/*.(js)":[ "pretty-quick--staged", "eslint--ext.js", "gitadd" ], "run/*":[ "gitrm--cached" ] }, "husky":{ "hooks":{ "pre-commit":"npmrunbuild&&gitadd.&&lint-staged" } } 复制2.配置.

  • 24个简单、好看的可视化图表用法介绍!数据分析小白必看

    最近经常和朋友聊起可视化的事情,发现不少人新手经常不会选择合适的图表,从而导致做出来的数据分析报告不尽如人意,今天就针对图表选择来分享一些技巧要让可视化图表达到给使用者最佳的信息传达效果,我们必须认真考虑各种规划和设计各种元素而图表种类繁多,如何选择正确的图表达到“一图胜千言”的效果呢?我将图表分成几个大类,分别为「比较类、占比类、趋势类、相关类、地理」,大家可根据自己的目的选择适合的图表。一、对比类1、普通柱形图简介:普通柱形图使用垂直柱子显示类别之间的数值比较,其中柱状图的一个轴显示正在比较的类别,而另一个轴代表对应的刻度值特点:不适合对超过10个类别的数据进行比较,且分类标签过长时建议使用条形图2、对比柱形图简介:对比柱形图使用正向和反向的柱子显示类别之间的数值比较。其中图表的一个轴显示正在比较的类别,而另一轴代表对应的刻度值。特点:用于展示包含相反含义的数据的对比,若是不是相反含义的建议使用分组柱形图。3、分组柱形图简介:分组柱状图经常用于相同分组下,不同类数据的比较。用柱子高度显示数值比较,用颜色来区分不同类的数据。特点:相同分组下,数据的类别不能过多。4、堆积柱形图简介:堆

  • SAP /usr/sap//DVEBMGS00满了怎么处理

    正文部分参考:Note16513-Filesystemisfull-whatdoIdo? 1.stat.DAT---性能统计文件。 对应的OS路径:x:\usr\sap\\DVEBMGS00\data\stat.DAT 处理方法:1.ST03->Workload->Reorganization->DeleteStatsFile 2.ST03N->Administrator->ExpertMode->CollectorandPerfromanceDB->StatisticsRecordsandfile->Deletefile 2.dev_rd--gatewaytracefile. 对应的OS路径:x:\usr\sap\\DVEBMGS00\work\dev_rd 处理方法:SMGW->Goto->Trace->Gateway->Resetfile 3.dev_rc--RFCtracefile 对应的OS路径:x:\usr\sap\\DVEBMGS00\work\dev_rfc(n) 处理方法:SM59-&

  • ES 自定义打分

    ES自定义打分Elasticsearch会为query的每个文档计算一个相关度得分score,并默认按照score从高到低的顺序返回搜索结果。在很多场景下,我们不仅需要搜索到匹配的结果,还需要能够按照某种方式对搜索结果重新打分排序。例如:•搜索具有某个关键词的文档,同时考虑到文档的时效性进行综合排序。•搜索某个旅游景点附近的酒店,同时根据距离远近和价格等因素综合排序。•搜索标题包含elasticsearch的文章,同时根据浏览次数和点赞数进行综合排序。Functionscorequery就可以让我们实现对最终score的自定义打分。score自定义打分过程为了行文方便,本文把ES对query匹配的文档进行打分得到的score记为query_score,而最终搜索结果的score记为result_score,显然,一般情况下(也就是不使用自定义打分时),result_score就是query_score。那么当我们使用了自定义打分之后呢?最终结果的score即result_score的计算过程如下:1.跟原来一样执行query并且得到原来的query_score。2.执行设置的自定义打分

  • 宝塔Linux面板专业版-安装与破解

    首先从安装宝塔Linux免费版开始,使用xshell或者其他软件连接到服务器上,执行一键安装命令脚本yuminstall-ywget&&wget-Oinstall.shhttp://download.bt.cn/install/install.sh&&shinstall.sh复制输入y安装安装完成记住账号密码之后登陆要用输入下面命令升级为专业版wget-Oupdate.shhttp://download.bt.cn/install/update_pro.sh&&bashupdate.shpro复制好了,下面就到了破解阶段我使用的是xftp(自行百度下载,这里就不提供了)连接服务器跳转到/www/server/panel/class 编辑 common.py 文件。在164行处将:data=panelAuth().get_order_status(None)复制替换为:data={ 'status':True, 'msg':{'endtime':32503651199}#授权结束时

  • 趣谈微服务之点-线-面关系

    摘要: 微服务是什么,是点?微服务化是什么,是线?微服务架构是什么,是面? 难道它们三者之间就是点-线-面这样简单的关系?可能你觉得这很扯吧,开始我也觉得这样描述不够恰当,但是后面思来想去,点-线-面简单且形象生动地说明这三者的概念及关系,也有助于读者理解和消化。不烦请您仔细往下阅读,看看是不是这个理儿。1.微服务-点从单体应用服务,到面向SOA(Service-OrientedArchitecture)服务,再到今天我们聊的微服务都是一样的,是对外提供服务的。 它们之间的区别: 在于服务体积(功能/模块)的大小,可能这里描述的不是很准确,但是意思差不多,依次是MicroServer<SOAServer<SingleServer。 因此,微服务强调的是服务的大小,形象的说就是一个点。而点也是有大小之分的。下面我们用图来展示三者的关系: 2.微服务化-线微服务化,这明显是向服务大小更小的服务演化,即系统从单体系统架构或面向SOA系统架构逐步向微服务架构演化的过程。为什么要微服务化,这种架构演进的意义何在? 2.1首先,我们来说一说,传统单体应用架构 以JavaWeb应用为例,

  • 大数据计算引擎,你 pick 哪个?

    不知道你是否有过和我类似的经历?我是2018年6月加入公司,一直负责监控平台的告警系统。之后,我们的整个监控平台架构中途换过两次,其中一次架构发生了巨大的变化。我们监控告警平台最早的架构如下图所示:这个架构的挑战难点在于:海量的监控数据(Metric&Log&Trace数据)实时写入ElasticSearch;多维度的监控指标页面展示(Dashboard)查ElasticSearch的数据比较频繁;不断递增的告警规则需要通过查询ElasticSearch数据来进行判断是否要告警。从上面的几个问题我们就可以很明显的发现这种架构的瓶颈就在于ElasticSearch集群的写入和查询能力,在海量的监控数据(Metric&Log&Trace数据)下实时的写入对ElasticSearch有极大的影响。我依然清楚记得,当时经常因为写入的问题导致ElasticSearch集群挂掉,从而让我的告警和监控页面(Dashboard)歇菜(那会老被喷:为啥配置的告警规则没有触发告警?为啥查看应用的Dashboard监控页面没数据)。我也很无奈啊,只想祈祷我们的ElasticS

  • 2018年开源社区十大法律事件

    本期编辑:EE自由和开源软件在2018年发生的法律问题将会在2019年及以后继续产生影响。2018年,当IBM以340亿美元的价格收购红帽时,我们看到了自由和开源软件(FOSS)商业模式的重要性。伴随着“开放源码促进会”(OpenSourceInitiative,OSI)庆祝开源运动20周年,自由和开源软件生态系统也在去年展示了其持久性。同时,旧有的法律问题又回来了。我们看到涉及自由和开源软件问题的诉讼判决再次显著增加,而其中一些案件非常重要。诉讼的增加提醒人们,对于所有使用自由和开源软件的公司(现在几乎所有公司都是如此)制定积极合规计划的重要性。继续着回顾过去、展望未来趋势的传统,以下是2018年自由和开源软件社区的十大法律事件。01— 来自德国的Linux系统版权流氓McHardy又回来了 PatrickMcHardy是Linux系统的早期贡献者,他一直利用德国的诉讼威胁来获得金钱赔偿,基本上就像一个版权流氓(copyrighttroll)。McHardy已经活跃了五年,据信接触过80多家公司。由于德国法院程序是保密的,许多公司在没有经过法院诉讼的情况下可能已经选择和解,准确数字很

  • 程序员偷偷深爱的 9 个不良编程习惯

    我们曾经都做过这样的事情:当妈妈不注意的时候,偷偷地吃糖果零食,然后导致有了蛀牙。同样的,我们都违背过一些编程的基本规则,并且都会坚定地表示这种行为是不可取的。但我们就是偷偷爱着这些不良的编程习惯。我们对所谓的编程规则嗤之以鼻,输出的代码也很糟糕——但我们依然活着。编程上帝没有下闪电劈死我们,我们的电脑也没有爆炸。事实上,只要我们能编译和发布代码,客户似乎就很满意了。这是因为糟糕的编程不像安装电路或者摸老虎屁股那样有直接的危害性。大多数时间里它也是可以工作的。规则通常是作为一种指导或格式上的建议,并没有硬性规定一定要遵守,也不会导致代码马上死掉。当然,你的代码可能会被人耻笑,甚至可能大家公开嘲笑你,不过,这种挑战惯例的行为可以让人增加一点颠覆传统的快感,哪怕是在不经意间。为了让问题变得更加复杂,有时候违反规则反而更好。(一般人我不告诉他!)出来的代码会更干净,甚至可能会更快和更简单。规则通常显得太过于宽泛,有技巧的程序员可以通过打破这些规则来提高代码。不要告诉你的老板,这对你的编码生涯会很有意义。下面这9个编码习惯,虽然在编程规则中是被驳斥的,但我们很多人就是会不由自主地使用它们。编程

  • 【机器学习】CS229课程笔记notes1翻译-Part II分类和logistic回归

    CS229课程笔记吴恩达PartII 分类和logistic回归   我们现在谈论分类问题。分类问题与回归问题类似,区别是在分类问题中,我们现在想要预测的y值只取少量的离散值。现在,我们聚焦于二值分类问题,y只取两个值,0和1。(我们在这里说的大多数可以扩展到多分类问题。)例如,如果我们试图构建一个垃圾邮件分类器,x(i)可能是一封邮件的某些特征,如果邮件是垃圾邮件,y为1,如果不是垃圾邮件,y为0。0也叫做负类,1叫做正类,它们用符号“-”和“+”表示。给定x(i),相应的y(i)也叫做训练样本的标签。5 Logistic回归   我们可以尝试解决分类问题,忽略y是离散值的事实,使用我们之前的线性回归算法试图预测给定x的y的值。然而,很容易构建这样的例子,但是这种算法的性能非常差。直观地,对于hθ(x),取值大于1或小于0没有意义,我们知道,y∈{0,1}。   为了解决分类问题,让我们改变我们的假设hθ(x)的形式。我们将选择   其中   这叫做logistic函数,或sigmoid函数,下面是g(z)的描点图像:   注意,当z-->∞时,g(z)趋向于1,当z-->

  • RTSP 资料

    分享两个不错的播客。 http://blog.csdn.net/u010425035/article/details/10410851 http://blog.csdn.net/xiaoyafang123/article/details/52197986 http://www.mamicode.com/info-detail-1444337.html  

  • 【android】移植IOS视图响应陀螺仪交互行为

    IOS有个很有趣味的特性:背景图片可以响应陀螺仪方向的变化,去改变X、Y轴上的值,从而让整个界面看着充满着灵性。具体步骤是:解锁苹果产品,在IOS7以上,摆动手势,观察桌面背景图片的变化。   刚好,我们的产品现在遇到了一个场景:标题栏以下,占据40%空间的是一张png图片,背景是一片星空,如果不给点交互,感觉太死板了 这时候想,如果把IOS这个特性移植到本场景中,作用对象是背景那个星空,那多美啊~ 二话不说,跪求美工大哥把png图片的前景和背景分离,拿到两张图片,开搞~   实现之后的效果产品大哥也觉得很赞,就把这套方案共享出来了,调用很简单,一共三句:声明、注册、解注册。 本模块工作原理:监听加速器里的陀螺仪传感器,获取其在x、y轴上的偏移数据,换算成一个垂直、水平上的位移值,赋值给视图的x、y属性。 先来看下效果,比较渣,建议下载APKdemo体验;源码地址:http://git.oschina.net/yso/IOSParallelView   一句话讲解陀螺仪xyz方向:以portrait屏幕方向为例,手机的左下角为原点,x轴:水平方向,越右越

  • 嵌入式编程中,如何使用复杂指针?

    1.说明 在C语言编程中,指针是最容易出错的地方,尤其是在很多指针同时出现的时候,看的眼花缭乱的,本文从嵌入式中常用的复杂角度进行分析,彻底搞清楚C语言中的容易弄错的指针使用问题。   2.函数指针与指针函数 在C语言中,函数是有他的地址,同理,函数有也有他的地址,如果如果我们把函数的地址赋值给函数指针,那么我们就可以间接的通过函数指针调用函数地址了。   函数指针的定义如下:   数据类型(*fun)(参数列表); 由于()的优先级高于*。   指针函数的定义如下:   数据类型*fun(参数列表); 其返回值为数据类型*。   实例:通过函数指针调用函数指针   第一步:定义函数指针   int*(*pfun)(int*,int*); 这里调用了一个数据类型为int*的函数指针,其中两个参数为两个int*。   第二步:定义指针函数   int*fun(int*,int*); 这里函数的返回值是int*。   第三步:实现函数指针   int*fun(int*a,

  • Loadrunner Sokcet压力测试接收变长数据的处理

    目前知道两种方式,我采用了第一种 1.分两次接受数据 参考http://blog.csdn.net/rachel_luo/article/details/7912468 第一次lrs_receive_ex接受与server约定好的保存长度的字节数, 我的case是前5个字节固定,其中前4个字节表示length,第5个字节表示type 于是我就调用lrs_receive_ex(sock_desc,buf_desc,"NumberOfBytesToRecv=5",LrsLastArg); 第一次先从接受缓冲区中读5个字节的数据出来 然后再调lrs_receive_ex(sock_desc,buf_desc,szBytesLength,LrsLastArg); 其中szBytesLength是从第一次接收的数据中计算出的后续部分的长度 这样就可以把整条数据分两次读完了   2.如果不需要知道数据的长度或者内容,可以一次接受完整条数据 参考http://blog.csdn.net/barebear/article/details/76713946 使用lrs_set_receive_

  • linux 的 ~/.bashrc

    vim~/.bashrc aliaspython=/home/wb-zf485783/.pyenv/versions/3.8.5/bin/python aliaspip=/home/wb-zf485783/.pyenv/versions/3.8.5/bin/pip

  • react入门(五):事件处理、条件渲染、列表&amp;keys、表单

    一、事件处理 React事件绑定属性的命名采用驼峰式写法,而不是小写。 直接看代码 两种方式绑定事件并传参数 第一种: constructor(props){ super(props); //在dom上用bind函数绑定了this,这里可以省略 this.handleClick=this.handleClick.bind(this); } handleClick(value,e){ //e要写在value后面 console.log(value);//2020/1/13下午7:09:35 console.log(e.target);//<button>handle</button> } <buttononClick={(e)=>{this.handleClick.bind(this,this.state.time)}}>handle</button> 第二种(更倾向于第二种) handleClick=(value,e)=>{ console.log(value);//2020/1/13下午7:09:35 con

  • 居家办公提高工作效率的八点建议

       今年由于受新型冠状病毒的影响,年假多放3天,持续到2月2日,由于新型冠状病毒的潜伏期是2~14天,各地为了有效防控疫情的蔓延,各省纷纷出台政策,除防疫及生活必须品生产企业,其他企业一律延期至2月9日24时后复工,所以从2月3号开始,部分企业组织员工进行居家办公了,从昨天到今天,已经有两天了,相信大家都有相同的感受,精力无法集中,团队协作效率明显降低,总想休息或者玩耍,工作效率十分低,下面我结合我居家办公的一些做法,给大家8点建议,希望可以帮助大家尽快的进入工作状态,提高工作效率。 一、饮食起居要有规律。即使在家办公,也要按时起床、吃饭、休息,具体时间可以参考公司的上班时间,另外在家吃饭,切忌吃的太饱,否则容易瞌睡懒惰,七分饱就可以了。   二、着装要正式。不要因为在家办公,就穿家居服或者睡衣,这样会潜意识的告诉自己现在是非工作状态,影响工作效率,建议换一套平时上班时穿的衣服,包括鞋子等,告诉自己,现在是工作状态了。   三、工作区与休息区要分开。比如不要再办公区玩电脑,不要再床上看书等。   四、制定日计划及周计划。首

相关推荐

推荐阅读