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

合并链表转化为环问题
服务器君一共花费了154.577 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本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

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

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

《大话设计模式》 程杰 (作者)

《大话设计模式》通篇都是以情景对话的形式,用多个小故事或编程示例来组织讲解GoF(设计模式的经典名著——Design Patterns: Elements of Reusable Object-Oriented Software,中译本名为《设计模式——可复用面向对象软件的基础》的四位作者Erich Gamma、Richard Helm、Ralph Johnson,以及JohnVlissides,这四人常被称为GangofFour,即四人组,简称GoF)总结的23个设计模式。本书共分为29章。其中,第1、3、4、5章着重讲解了面向对象的意义、好处以及几个重要的设计原则;第2章,以及第6到第28章详细讲解了23个设计模式;第29章是对设计模式的全面总结。

更多计算机宝库...