之前的一篇博客《 如何判断两条单链表是否有交点 》只说了如何判断是否有交点,但并没有提及如何得到交点。
设置数组分别存储两条链表所有节点的地址,然后一 一比较?可行是可行,不过空间时间复杂度太高,不建议使用。
那有没有更高效的方法呢?
方法1
从相交链表的特点来切入分析,看看下面这张图。

一般来说,相交链表会自相交点后有一段公共区域。绿色圈起部分。然而这两条红色A和蓝色B链表的长度差别是不是就是进入公共区域前的长度差?排除特殊情况(两条链表长度相等),总会有一个链表比另一个链表长,如果让比较长的链表提前走过长度差的距离(粉色lenA-lenB),然后再让两条链表开始同步往后走,他们就会同步到达相交点,这样判断不就轻松多了?如果两条链表长度相等,两者同时走就好了。
建立个案例测试下。


获取单链表交点代码如下


方法2
上篇博客才说的 环 的问题《
单链表有关 环 的问题》,是否可以联系一下?
让A链表遍历到尾巴,然后让A链表的尾结点指向B链表的头节点。
问题就转变为求A链表的入环点问题了。是不是很有灵性呢?


最后
以上就是冷酷大地最近收集整理的关于如何获取两个单链表交点的全部内容,更多相关如何获取两个单链表交点内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复