判断链表相交

作者：weixin_40725706 | 2024-06-08 13:29:23

踩

判断链表相交

题目

给定两个链表，判断是否相交

总述：

1. 找到两个链表各自的入环点node1和node2
2. 如果node1和node2有一个为空，另一个不为空，则两个链表不可能相交
3. 如果node1和node2都等于空，说明两个链表都无环，则可以利用判断两个无环链表求取第一个相交点的方法求取
4. 如果node1和node2都不为空，说明两个链表都有环，需要分情况讨论

入环点相同且是第一个相交的结点
入环点相同且不是第一个相交的结点
入环点不同，如果一个入环点在回到自身的过程中遇到了另外一个链表的入环点则相交，否则不想交。相交的情况下可以返回任意一个入环点作为第一个相交点

1、两个链表都没有环，判断相交（链表的相交指的是地址相同，不是结点中的对象相等）
两个无环链表相交则两个链表的最后一个结点必定相等


/**
 * 现在有两个无环单链表，若两个链表的长度分别为m和n，
 * 请设计一个时间复杂度为O(n + m)，额外空间复杂度为O(1)的算法，判断这两个链表是否相交。
 * 给定两个链表的头结点headA和headB，请返回一个bool值，

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/689948