如何判断两链表是否相交

如何判断两链表是否相交，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

创新互联是专业的麻江网站建设公司，麻江接单;提供成都网站建设、网站制作,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行麻江网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

给定两单链表A、B，只给出两头指针。请问：

1、如何判断两单链表（无环）是否相交？

有两种可取的办法：

（1）人为构环，将链表A的尾节点指向链表B，再判断是否构环成功？从链表B的头指针往下遍历，如果能够回到B，则说明相交

（2）判断两链表最后一个节点是否相同，如果相交，则尾节点肯定是同一节点

2、如何判断两单链表（不知是否有环）相交？

先判断是否有环，判断是否有环可以使用追逐办法，设置两个指针，一个走一步，一个走两步，如果能相遇则说明存在环

（1）两个都没环：回到问题1

（2）一个有环，一个没环：不用判断了，肯定两链表不相交

（3）两个都有环：判断链表A的碰撞点是否出现在链表B的环中，如果在，则相交。（相交时，环必定是两链表共有的）

3、如何寻找两相交链表（不知是否有环）的第一个相交节点？

同样，使用追逐办法先判断是否存在环，分情况讨论

（1）无环：人为构环，将链表A的尾节点指向链表B，则构成一个带环的单链表。这个问题就转换成寻找带环单链表的环入口节点。

    解法参考：连接点此

（2）有环：计算出两链表的长度lA、lB，（环的长度和环到入口点长度之和就是链表长度）

计算带环链表长度，可参考http://blog.csdn.net/liuxialong/archive/2011/06/20/6555850.aspx

如果lA>lB，则链表A指针先走lA-lB，然后链表B指针开始走，两者相遇的点就是相交点

如果lB>lA，则链表B指针先走lB-lA，然后链表A指针开始走，两者相遇的点就是相交点

链表有环否 也可参考此处  是否有环

看完上述内容，你们掌握如何判断两链表是否相交的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注创新互联行业资讯频道，感谢各位的阅读！

当前标题：如何判断两链表是否相交
分享网址：http://scjbc.cn/article/gsdsig.html