2
条回答
写回答
写回答
-
有点尴尬唉 你要寻找的东西已经被吃掉啦！两个链表，判断是否相交，找出相交的第一个点？
首先应该清楚两个单链表相交要么都是无环链表，要么都是有环链表，不存在一个有环链表和一个无环链表相交，因为两个链表一旦相交则后续的链表都应该是相同的（1）将其中任意一个链表的环打破，即让尾结点指向null（记下保存原本应当指向的位置），然后判断第二个链表是否含有环，若第二个链表无环则相交，否则不相交
（2）利用判断单链表是否有环的方法，对链表使用两个快慢指针进行判断是否有环，两个指针的碰撞点即在环上，那么判断链表二的环上是否包含该碰撞点就可以判断两个链表是否相交了
2020-04-15 22:51:12赞同 1 展开评论 打赏 -
参考答案： $O(n^2)$: 两层遍历，总能发现是否相交
$O(n)$: 一层遍历，遍历完两个链表，如果两个链表的最后一个结点指针相同，则相交，否则不相交
2020-04-14 18:34:50赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
