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

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

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

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

《算法导论(原书第2版)》 科曼(Cormen T.H.) (作者), 等 (作者, 译者), 潘金贵 (译者)

《算法导论(原书第2版)》一书深入浅出,全面地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通子图算法正确性的证明,对哈密顿回路和子集求和问题的NP完全性的证明等内容。全书提供了900多个练习题和思考题以及叙述较为详细的实例研究。

更多计算机宝库...