判断两个单链表是否交叉

利用两个链表交叉的性质,若两个链表交叉,从链表的交叉点到链表尾部,都是相同的节点,因此,链表形状是Y型。

具体做法:首先计算出两个链表的长度之差,n,让长的链表先移动n步,短的链表再依次向后遍历,这样它们同时到达第一个公共节点,在向后移动的过程中比较两个链表的节点是否相等就可以获得第一个公共节点。时间复杂度是O(m+n)(链表长度分别为m,n)

2.人为构环,将链表A的尾结点指向链表B,判断是否构成环,从链表B的头指针往下遍历,如果能够回到B,则说明相交。

通过判断最后一个节点是否相等来判断是否交叉。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 搞懂单链表常见面试题 Hello 继上次的 搞懂基本排序算法,这个一星期,我总结了,我所学习和思考的单链表基础知识...
    醒着的码者阅读 4,653评论 1 45
  • 专业考题类型管理运行工作负责人一般作业考题内容选项A选项B选项C选项D选项E选项F正确答案 变电单选GYSZ本规程...
    小白兔去钓鱼阅读 9,090评论 0 13
  • 算法思想贪心思想双指针排序快速选择堆排序桶排序荷兰国旗问题二分查找搜索BFSDFSBacktracking分治动态...
    第六象限阅读 3,426评论 0 0
  • 勤勤路上感, 只是为上班。 日出忘忘叹, ...
    符白雲阅读 227评论 0 1
  • 从1972年首次出版,如今已经在世界各地畅销四十多年。在读书届享负盛名,然而,读起来却并不轻松,甚至对大多数普通读...
    静静文阅读 238评论 0 4