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

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

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

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

《敏捷软件开发(原则模式与实践)》 马丁 (作者), 邓辉 (译者)

《敏捷软件开发:原则模式与实践》由享誉全球的软件开发专家和软件工程大师Robert C.Martin将向您展示如何解决软件开发人员、项目经理及软件项目领导们所面临的最棘手的问题。这本综合性、实用性的敏捷开发和极限编程方面的指南,是由敏捷开发的创始人之一所撰写的。1.讲述在预算和实践要求下,软件开发人员和项目经理如何使用敏捷开发完成项目;2.使用真实案例讲解如何用极限编程来设计、测试、重构和结对编程;3.包含了极具价值的可多次使用的C++和JAVA源代码;4.重点讲述了如何使用UML和设计模式解决面向客户系统的问题。

更多计算机宝库...