题目:
一个比较经典的问题,判断两个链表是否相交,如果相交找出他们的交点。
首先来看一下如何判断两个链表是否存在相交的节点:
思路:
1、碰到这个问题,第一印象是采用hash来判断,将两个链表的节点进行hash,然后判断出节点,这种想法当然是可以的。
2、当然采用暴力的方法也是可以的,遍历两个链表,在遍历的过程中进行比较,看节点是否相同。
3、第三种思路是比较奇特的,在编程之美上看到的。先遍历第一个链表到他的尾部,然后将尾部的next指针指向第二个链表(尾部指针的next本来指向的是null)。这样两个链表就合成了一个链表,判断原来的两个链表是否相交也就转变成了判断新的链表是否有环的问题了:即判断单链表是否有环?
这样进行转换后就可以从链表头部进行判断了,其实并不用。通过简单的了解我们就很容易知道,如果新链表是有环的,那么原来第二个链表的头部一定在环上。因此我们就可以从第二个链表的头部进行遍历的,从而减少了时间复杂度(减少的时间复杂度是第一个链表的长度)。
下图是一个简单的演示:
这种方法可以判断两个链表是否相交,但不太容易找出他们的交点。
4、仔细研究两个链表,如果他们相交的话,那么他们最后的一个节点一定是相同的,否则是不相交的。因此判断两个链表是否相交就很简单了,分别遍历到两个链表的尾部,然后判断他们是否相同,如果相同,则相交;否则不相交。示意图如下:
在来看一下如何找出第一个相交点:
思路:
1. 判断出两个链表相交后就是判断他们的交点了。假设第一个链表长度为len1,第二个问len2,然后找出长度较长的,让长度较长的链表指针向后移动|len1 - len2| (len1-len2的绝对值),然后在开始遍历两个链表,判断节点是否相同即可。
2. 还有一种方案是,是在上面的问题中的解决方案3中将一个链表的尾节点链接到第二个链表的头结点,如果两个链表有共同的交点的话,一定存在环,那么这时候我们就可以找到环的入口节点,就是两个链表的相交的第一个节点。
总结
上面的几种方法中最后一种是比较不错的,当然hash也是可以的。
问题的延伸:
如果原来的两个链表中有环怎么处理?
分享到:
相关推荐
分析与解法 这样的一个问题,也许我们平时很少考虑。但在一个大的系统中,如果出现两个链表相 交的情况,而且释放了其中一个链表的...的两个链表,我们希望在释放一个链表之前知道是否有其他链表跟当前这个链表相交。
给出两个单向链表的头指针(如图3-8 所示),比如h1、h2,判断这两个链表是否 相交。这里为了简化问题,我们假设两个链表均不带环。
数据结构与算法----线性表及Java实现顺序表、链表、栈、队列 定义线性表节点的结构.pdf
算法-数据结构和算法-6-链表和单链表的实现过程.rar
可以看到如果把h1链表的尾节点的next指针指向h2链表的第一个节点,那么可以看到如果h1和h2相交,则h2变成了一个循环单链表,因此只需判断h2是否为循环链表
链表实战题目4 - 链表入环的第一个节点给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 null。为了表示给定链表中的环,我们使用整数 pos
嵌入式学习-02-数据结构和算法 (链表)
算法-数据结构和算法-8-双向链表.rar
算法大全-面试题-链表-栈-二叉树-数据结构.docx 一、单链表 目录 1.单链表反转 2.找出单链表的倒数第4个元素 3.找出单链表的中间元素 4.删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级...
1.3.9 如何判断两个链表是否相交
双向链表 - 数据结构与算法 C 双向链表 - 数据结构与算法 C 。。。。。。
实现两个链表的合并(数据结构课程设计c语言版)
# 将第一个节点指向第三个节点# 第二个节点指向第一个节点# 节点first指向第二个节点# 当前节点后移动,记得a.next是节点3,相当于跳了一个节点,往后
数据结构-基本算法-静态链表(学生时代源码,调试可运行)
这份资料里面讲解的很清楚详细,易懂,对正在学习编程的同学特别是对正在找工作的同学非常有帮助。
数据结构-基本算法-孩子兄弟链表(学生时代源码,调试可运行)
算法-数据结构之链表合并算法.rar
数据结构与算法 c语言 线性表-静态链表 静态链表源码