剑指offer(三十六)-两个链表的第一个公共结点(Java版)_java判断两个链表是否有公共部分-程序员宅基地

技术标签: 剑指offer  java  链表  leetcode  链表的公共节点  数据结构  

描述

输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)

 

示例1

输入:{1,2,3},{4,5},{6,7}

返回值:{6,7}

说明:第一个参数{1,2,3}代表是第一个链表非公共部分,第二个参数{4,5}代表是第二个链表非公共部分,最后的{6,7}表示的是2个链表的公共部分

这3个参数最后在后台会组装成为2个两个无环的单链表,且是有公共节点的

示例2

输入:{1},{2,3},{}

返回值:{}

说明:2个链表没有公共节点 ,返回null,后台打印{}

第一种解法

第一种方法很简单,直接遍历两个链表,将第一个链表的结果存进集合里面,遍历第二个链表的时候,直接在集合里面判断即可。代码如下

public ListNode firstFindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(null == pHead1 || null == pHead2){
            return null;
        }
        ArrayList<ListNode> listNodes = new ArrayList<>();
        while (pHead1 != null){
            listNodes.add(pHead1);
            pHead1 = pHead1.next;
        }
        while (pHead2 != null){
            if(listNodes.contains(pHead2)){
                return pHead2;
            }
            pHead2 = pHead2.next;
        }
        return null;
    }

第二种解法

第二种解法,我们需要明白一个事情,公共结点是指相同节点以后的所有节点都相同,举个例子(1,2,5,7和8,9,4,5,7是有公共节点的,但是1,2,5,7和8,9,4,5,7,15就不符合题目公共节点的要求了),所以我们可以将p1和p2链表进行拼接,即(p1+p2组成新的p1,p2+p1组成新的p2,这样拼接以后,p1和p2的长度一定是一致的,如果它们有公共节点,那么新的p1和p2最后的节点一定相同,否则不存在公共节点),代码如下

public ListNode secondFindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(null == pHead1 || null == pHead2){
            return null;
        }
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while (p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
            if(p1 != p2){
                if(p1 == null){
                    p1 = pHead2;
                }
                if(p2 == null){
                    p2 = pHead1;
                }
            }
        }
        return p1;
    }

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/juanqiao7497/article/details/120459100

智能推荐

【工作】python识别不同国家语言类型_langid识别出的tl是什么语种-程序员宅基地

文章浏览阅读6.6k次,点赞4次,收藏15次。优秀文章推荐:地址:Python使用谷歌langdetect检测语言地址:Python3:语言探测工具langdetect和langid支持的语言类型:支持检测55种语言: af, ar, bg, bn, ca, cs, cy, da, de, el, en, es, et, fa, fi, fr, gu, he, hi, hr, hu, id, it, ja, kn, ko..._langid识别出的tl是什么语种

python之Rich库使用入门(打印彩色字体,表单,进度条与状态动画,高级数据类型)_python rich-程序员宅基地

文章浏览阅读2w次,点赞31次,收藏106次。文章目录前言一、Rich是什么?二、使用步骤1.Rich安装2.读入数据总结前言最近发现了一款非常强大的python第三方库——Rich这款库主要用于终端打印一、Rich是什么?Rich是一个Python库,用于将丰富的文本(带有颜色和样式)写入终端,并用于显示高级内容,例如表格。使用Rich使您的命令行应用程序更具视觉吸引力,并以更具可读性的方式呈现数据。Rich还可以通过漂亮的打印和语法突出显示数据结构来作为有用的调试辅助工具。二、使用步骤1.Rich安装直接pip就好了pip_python rich

谁是华为扫地僧?-程序员宅基地

文章浏览阅读203次。是的,华为也有扫地僧!2020年2月11-12日,“养在深闺人不知”的华为2012实验室扫地僧们,将在华为开发者大会2020(Cloud)上,和大家见面。到时,你可以和扫地僧们,吃一个洋气的Brunch(早午餐),并和他们面对面,围绕某个课题探讨技术。别看扫地僧这个名字很接地气,他们的真实身份大多是博士、Fellow和教授,都是来自华为各领域最顶尖、最优秀的技术专家。构建一云两翼双引擎+开放的生态在1月8日的华为开发者大会2020(Cloud)媒体预沟通会..._华为扫地僧

服务器知识和维护,服务器维护知识-程序员宅基地

文章浏览阅读244次。服务器维护知识 内容精选换一换旨在推动鲲鹏计算人才的培养,面向鲲鹏计算工程师提供芯片技术基础知识、计算系统架构、操作系统、鲲鹏产品、应用移植相关内容培训,内容包含芯片介绍,欧拉操作系统介绍,鲲鹏服务器产品培训、服务器管理、配置与部署,日常维护、典型问题处理等,使学员具备产品的规划设计、安装部署、运维和故障处理等能力,了解欧拉操作系统、应用移植基本知识,具备胜任鲲鹏计算为加强对系统数据的容灾管理,云..._服务器维护工程师学习资料

MySQL死锁解决_mysql trx_rows_locked: 1774-程序员宅基地

文章浏览阅读195次。查看mysql存储引擎模式:SHOW ENGINES;查看事务提交模式:SHOW SESSION VARIABLES LIKE ‘autocommit’;SHOW GLOBAL VARIABLES LIKE ‘autocommit’;Value的值为ON,表示autocommit开启。OFF表示autocommit关闭。查看锁记录等待时间:SHOW VARIABLES LIKE ‘innodb_lock_wait_timeout’;把超时等待时间修改为5秒:SET innodb_lock__mysql trx_rows_locked: 1774

由国家土地流转政策想到的-程序员宅基地

文章浏览阅读2.6k次。最近国家出了一个土地自由流转的正常,我发现这个想法跟我在05年写了博客《构建高效率的农业构架》(http://blog.csdn.net/sunlen/archive/2005/08/28/466916.aspx)想法基本上是一样了,并且听说政府前一两年就开始在做试点了,可见政府早就知道这个问题了,不过现在政府提出来的也只不过我提出想法的初步实现而已,等农业搞到高级阶段,有3亿农民就已经绰绰有余了

随便推点

java第八节笔记-程序员宅基地

文章浏览阅读358次。第八节一、instanceof 实例判断,用来判断有没有此类的类型equals 比较对象一般判断步骤1.先判断内存是否一致,2.判断是否是此类3.判断各属性是否相等。克隆:clone() 如:直接new一个对象,将属性值赋予它。Final 常量关键字。 1.修饰变量变量是常量 2.修饰属性上属性是常量 3.修饰方法上方法不可重写,修饰在类

51 Proteus仿真频率计速度计超速报警数码管显示MAX7219-0001_proteus频率计怎么用-程序员宅基地

文章浏览阅读678次。51 Proteus仿真频率计速度计超速报警数码管显示MAX7219-0001硬件组成:51单片机 +8位数码管+MAX7219数码管驱动模块++多个按键+LED灯+蜂鸣器1.准确测量信号发生器输出的方波频率信号(速度)(0~10KHz),然后显示在数码管上面。2.可以通过按键设定报警频率(速度),当速度超过设定报警值后,蜂鸣器器报警并且LED灯亮。3.有4个按键分别是:速度设置、增大、减小、确定。点击速度设置键可以进入速度设置模式。_proteus频率计怎么用

Anypoint Studio配置runtimes_studio-runtimes-程序员宅基地

文章浏览阅读3.1k次,点赞2次,收藏3次。Anypoint Studio配置runtimesAnyPoint Studio这个工具属于基于eclipse的集成工具。该工具是是免费的,但是运行环境是分为社区版和企业版的,企业版的是收费的,免费30天使用。查看自己的软件版本和自带的runtimes版本。v7.2.1只支持mule4.1以上的版本。Anypoint Studio默认自带的runtimes都是企业版的。适用时间为一个月..._studio-runtimes

频响特性曲线_OEP30W频率特性测量-程序员宅基地

文章浏览阅读990次。简介在博文"OEP30W D 类音频功率放大器简单测试”中给出了 OPE30W 的基本连接方式和功能应用。对于该音频放大芯片的输出特性和温度特性是什么?本文给出了测试方案。在测试芯片的频率相应的时候,需要使用到正弦波产生芯片模块 AD9833。所使用到的 COM2 串口命令如下所示:from tsmodule.tshardware import *ccloadSerial.write(b'a..._oep30wx2资料

Mac下Android studio 运行真机-程序员宅基地

文章浏览阅读582次。一·配置adb打开Android studio的终端窗口,输入adb。如果显示command not found..._android studio flamingo mac真机运行

opporeno5可以用鸿蒙系统,OPPO Reno5 Pro+超大杯曝光 首发旗舰IMX766-程序员宅基地

文章浏览阅读2.6k次。中关村在线消息:12月21日,OPPO官方发布了这款机型的预热海报,并且表示,OPPOReno5 Pro+将采用与索尼联合研发的旗舰传感器——IMX766,这将开启全能影像新体验。据了解,OPPO Reno5 Pro+首发的索尼IMX766为5000万像素,CMOS尺寸约为 1/1.5英寸。回想上一代Reno4 Pro,采用了索尼定制版IMX708传感器,拥有16:9定制视频画幅、120度超广角..._reno5pro可以刷别的系统吗?

推荐文章

热门文章

相关标签