编程判断两个链表是否相交

给出两个单向链表的头指针，而两个链表都可能带环，判断这两个链表是否相交，并且给出他们相交的第一个节点

参考

1)判断链表是否存在环
设置两个链表指针(fast, slow)，初始值都指向链表头结点，然后连个指针都往前走，不同的是slow每次前进一步，fast每次前进两步，如果存在环，两个指针必定相遇。

(2)若链表有环，找到环的入口点
当fast与slow相遇时，slow还没走完链表，而fast已经在环内循环了n圈了，假设slow在相遇前走了s步，则fast走了2s步，设环长为r，有2s=s+nr，即s=nr.

---

由上图可知a+x=s, x+y=r，而我们的目标是找到a的位置。设上图那个拱起的曲线的长度为y，有a+x=s=nr=(n-1)r+r=(n-1)r+y+x，则a=(n-1)r+y. 这个公式告诉我们，从链表头和相遇点分别设一个指针，每次各走一步，这两个指针必定相遇，且相遇的第一个点为环入口点。

(3)若两个链表都不存在环，找出两个链表相交的第一个节点

1. 将其中一个链表首尾相连，判断另一个链表是否存在环，如果存在，则两个链表相交，且找出来的环入口点即为相交的第一个点。
2. 首先遍历两个链表，记下两个链表的长度，长链表从起点先前进len_max-len_min步，然后两个链表再一起前进，每次一步，相遇的第一个点即为相交的第一个点。

(4)若两个链表都存在环，找出两个链表相交的第一个节点
通过方法(1)我们能够分别找出两个链表的相遇点pos1, pos2，然后还是使用两个指针fast和slow，都初始化为pos1，且fast每次前进2步，slow每次前进1步。若fast指针在遇到slow前，出现fast等于pos2或fast->next等于pos2，则说明两个链表相交，否则不相交。若两链表相交，我们可知pos2肯定是两个链表的一个相交点，将这个点看做两个链表的终止节点，使用(3)中的解法，即可找到两个链表相交的第一个节点。