判断两个链表是否相交的思路

合并链表转化为环问题
服务器君一共花费了656.505 ms进行了4次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

给出两个单向链表的头指针,比如h1,h2,判断这两个链表是否相交。(如图,假设两个链表均不带环)

思路一:

最直观的解法就是判断第一个链表中的每个节点是否在第二个链表中。这种方法的时间复杂度是O(Length(h1)*Length(h2))

思路二:哈希

对第一个链表的节点地址进行hash,建立长度为Length(h1)的哈希表。然后对第二个链表中的每个节点地址进行hash,在哈希表中查询,若在表中出现,则有共同节点,链表相交。

这种方法的时间复杂度是O(Length(h1)+Length(h2)),空间复杂度为哈希表的长度O(Length(h1)).

思路三:问题转换

将两个链表首尾相接,判断相接后的链表是否有,若有环,则说明两个链表相交;无环,则不相交。这里若有环,则第二个链表的表头一定在环上,则我们只需从第二个链表进行遍历,若走回到第二个链表的表头,则说明有环。注意,判断完后要将两个链表拆开。

这种方法时间复杂度是O(Length(h1)+Length(h2)),空间复杂度是常数。

思路四:

若两个单链表相交,则从相交节点之后两个链表后面的内容都是一样的,进而得出这两个单例链表最后一个节点一定是相同的。所以我们可以遍历第一个链表,找到最后一个节点,然后找到第二个链表的最后一个节点,相比较。

这种方法时间复杂度:O(Length(h1)+Length(h2)),且只需一个额外指针来存储第一个链表最后一个节点。

补充:若是链表有环,则先找出第一个链表最后一个节点p,遍历第二个链表,若p在第二个链表中,则相交;否则不想交。

本文地址:http://www.nowamagic.net/librarys/veda/detail/1843,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1843

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《深入理解MySQL核心技术》 Sasba Pacbev (作者), 李芳 (译者), 于红芸 (译者), 邵健 (译者)

《深入理解MySQL核心技术》:从公共可用性的意义上讲,MySQL源代码是开放源代码,但如果对其不了解,则实质上,它对于您来说是封闭的。MysQL开发团队的前成员Sasha Pachev通过《深入理解MySQL核心技术》给出了MySQL 5的全面指南,揭示了这一强大数据库的内部运作。您将直奔MySQL核心技术,了解各种数据结构和各种方便的功能的运作情况,了解如何添加新的存储引擎和配置选项等。 《深入理解MySQL核心技术》从结构概况讲起,在这一部分解释了MysQL的不同组件是如何协同工作的。接着将学习设置有效的可编译代码副本的步骤,然后使用基本架构添加自己的配置变量和存储引擎。

更多计算机宝库...