链表相交

链表相交

题目地址：https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/

题目的意思就是两个单链表，判断是否是相交链表，是的话，返回相交节点
当我看见这个题目的时候，第一想法就是暴力解决，用双层循环解决这个问题

代码如下图：

leetcode上也通过了，但是效率很低：

题解，看大佬的结题思路，下面自己总结下

1. 先上一张图

 

pic-1597720791149.png

 

1. 分析

假设两个链表相交，那么数据结构必然是上图所示，从相交节点之后，都是公共的链表部分，因为单链表的节点之后一个next，所以相交之后的部分必然相同。
定义两个指针：a和b，起初分别指向A链表的头结点和B链表的头结点。
当a指针后移到A链表最后一个节点的时候，那么让a指针重新指向B链表的头结点。（b指针同理，如下）
当b指针后移到B链表最后一个节点的时候，那么让b指针重新指向A链表的头结点。
这个时候，a指针和b指针在交点处O必然相遇。理由如下：
a指针走完A链表，再从B链表的头部开始走，走到交点O总共走的长度是：AO + OC + BO；
而b指针走完Bl链表，再从A链表的头部开始走，走到交点O总共走的长度是：BO + OC + AO;
根据以上分析，那么就可以很简单的推出链表是否相交的结论：
若相交第二次a指针从B链表头部开始，b指针A链表头部开始的遍历必然有相同引用。
若没有相同引用则必然不相交。

1. 上代码

 

pic-1597720791150.png