160.相交链表
发布日期:2021-10-12 21:31:51
浏览次数:1
分类:技术文章
本文共 456 字,大约阅读时间需要 1 分钟。
这道题很有意思,让我弄明白了关于链表的一些东西,怎么比较两个链表是否相等?不需要两个链表开始,一个一个地next去比较,我最初就陷进去了,后来我发现,只要直接比较这两个链表就好了。即直接l1 == l2,这样比较就行了。所以,就有了第一种做法,遍历l1链表,每次都将链表的地址放进map中,然后l1.next,接下来再第二个链表l2中也是一个个进行遍历,每次比较是否相等,代码如下:
不过很遗憾,这种做法并不是O(1)内存,因为新开了一个map
接下来就是我看到的题解,那种比较浪漫的解法了。假如两个链表从某个节点开始,那么从那个节点到最后都是相等的,也就是说这两个链表从同一个位置出发,假如要到达同一个终点的话,那么他们所走过的路都是相同的。那么,我们可以先求出两个链表的长度,然后,让长的那个链表先走两个链表的长度差的距离,这样就保证了到时候两个链表同时出发了,接下来只要在某个节点上发现两个链表相等,那么该节点就是他们的相交节点。如果不相等,则两个链表都向下走,假如最后都不相等,说明他们错过了。代码如下:
转载地址:https://blog.csdn.net/qq_40058686/article/details/104435307 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年03月27日 21时40分05秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
中国网建java发送短信_短信验证登陆-中国网建提供的SMS短信平台
2021-06-24
隔行变色java代码_jquery入门—选择器实现隔行变色实例代码
2021-06-24
webpack 入口文件 php,如何实现webpack多入口文件打包配置
2021-06-24
php tire树,Immutable.js源码之List 类型的详细解析(附示例)
2021-06-24
matlab转差频率控制,转差频率控制的异步电机调速系统的研究
2019-04-21
oracle错误1327,Oracle中的PGA监控报警分析(r11笔记第97天)
2019-04-21
php函数内的循环,PHP 循环列出目录内容的函数代码
2019-04-21
oracle树状排序,Oracle树状结构查询
2019-04-21
深度linux内核升级,深度操作系统 2020.11.11 更新发布:内核升级
2019-04-21
sql 拆解函数_SQL入门50题详解(含知识点讲解及代码运行步骤拆解)
2019-04-21
java和python交互 jni_Python基于pyjnius库实现访问java类
2019-04-21
mysql表名长度_JavaWeb之MySQL(一)
2019-04-21
mysql服务器语法_Mysql语法
2019-04-21