如何获取两个单链表交点

78 阅读 0 评论 52 点赞

我是靠谱客的博主冷酷大地，最近开发中收集的这篇文章主要介绍如何获取两个单链表交点，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

之前的一篇博客《如何判断两条单链表是否有交点》只说了如何判断是否有交点，但并没有提及如何得到交点。

设置数组分别存储两条链表所有节点的地址，然后一一比较？可行是可行，不过空间时间复杂度太高，不建议使用。

那有没有更高效的方法呢？

方法1

从相交链表的特点来切入分析，看看下面这张图。

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

建立个案例测试下。