【题目】

在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点headl和head2，这两个链表可能相交，也可能不相交。请实现一个函数，如果两个链表相交，请返回相交的第一个节点；如果不相交，返回null即可。

要求：如果链表1的长度为N，链表2的长度为M，时间复杂度请达到O（N + M，额外空间复杂度请达到O（1）。

【解题思路】

本题可以拆分成三个子问题，每个问题都可以作为一道独立的算法题，具体如下。

问题一：如何判断一个链表是否有环，如果有，则返回第一个进入环的节点，没有则返回null。

使用快慢指针即可，若快慢指针会相遇，则有环，否则快指针先到空节点；

此时，快指针从此处一次移一步遍历，慢指针从头结点开始遍历，两指针再次相遇时即为环的重合节点；

问题二：如何判断两个无环链表是否相交，相交则返回第一个相交节点，不相交则返回null。

两个链表分别遍历到最后一个非空节点，并记录其长度，若最后一个节点相同，则两链表相交，否则没有

然后再从头开始遍历，长链表先走差值步数，然后两个链表一起遍历，

当两指针指向相同一个节点，该节点就是开始相交的节点

问题三：如何判断两个有环链表是否相交，相交则返回第一个相交节点，不相交则返回null。

注意：如果一个链表有环，另外一个链表无环，它们是不可能相交的，直接返回null。

使用问题一中的方法分别找出每条链表的环的开始重合loop1,loop2

如果loop1==loop2怎表明连个环形链表不仅重合环形部位，而且前面还有重合线链部位，如图

怎么找到最开始的相交部位？在loop前的部位时，使用方法二即可找出

若loop1!=loop2

则loop1遍历循环，若loop1回到原位之前没有遇到loop2,则表明两个环形链表没有相交，如图2；

 

否则相交，如图3

 　　

代码很简单，后期补上