链表常见问题汇总

1.给一个单链表，判断其中是否有环的存在；
两个指针同时从头指针开始遍历链表，一个每次遍历一个，另外一个每次遍历两个，如果在遍历到尾指针之前相遇，说明有换，而且此时慢指针至多绕环刚好一圈。

vector_ring.png

2.如果存在环，找出环的入口点；
头节点到入口点的距离等于慢指针刚到入口点时快指针领先的距离，也等于两个指针相遇点到入口点的距离，所以一个从起点一个从相遇点走相遇的位置就是入口点。

3.如果存在环，求出环上节点的个数；
环上节点数等于两个指针第二次相遇时走的步数。

4.如果存在环，求出链表的长度；
链表长度=入口距离+环的长度

5.如果存在环，求出环上距离任意一个节点最远的点（对面节点）；
环长度的一半

6.（扩展）如何判断两个无环链表是否相交；
把其中一个首尾相连，遍历另外一个，如果有环说明有交集

7.（扩展）如果相交，求出第一个相交的节点；
就是求入口点，此外受链表逆序问题启发，还有一种解法 ：
设不相交部分为a,b，相交部分为c，那么首先遍历两个链表得到a+c和b+c的值，然后反转其中一个链表，再次遍历另外一个链表，就会得到a+b的值，要求c的值只需要解出这个三元一次方程组即可。