如何判断两个链表是否相交 -问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

如何判断两个链表是否相交

Runt 2020-04-14 18:34:41 1925

题目:如何判断两个链表是否相交

出题人:阿里巴巴新零售技术质量部

新零售
分享到
取消 提交回答
全部回答(2)
  • 景凌凯
    2020-04-15 22:51:12

    两个链表,判断是否相交,找出相交的第一个点?

    首先应该清楚两个单链表相交要么都是无环链表,要么都是有环链表,不存在一个有环链表和一个无环链表相交,因为两个链表一旦相交则后续的链表都应该是相同的
    

    (1)将其中任意一个链表的环打破,即让尾结点指向null(记下保存原本应当指向的位置),然后判断第二个链表是否含有环,若第二个链表无环则相交,否则不相交

    (2)利用判断单链表是否有环的方法,对链表使用两个快慢指针进行判断是否有环,两个指针的碰撞点即在环上,那么判断链表二的环上是否包含该碰撞点就可以判断两个链表是否相交了

    1 0
  • Runt
    2020-04-14 18:34:50

    参考答案: $O(n^2)$: 两层遍历,总能发现是否相交

    $O(n)$: 一层遍历,遍历完两个链表,如果两个链表的最后一个结点指针相同,则相交,否则不相交

    0 0
添加回答
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

推荐文章
相似问题
推荐课程