引言
单链表的尾环问题是一个比较经典的问题，它涉及的问题如下:
1>给一个单链表，判断其中是否有环的存在;
2>如果存在环，找出环的入口点;
3>如果存在环，求出环上节点的个数;
4>如果存在环，求出链表的长度;
5>如果存在环，求出环上距离任意一个节点最远的点(对面节点)；
6>(扩展)如何判断两个无环链表是否相交
7>(扩展）如果相交，求出第一个相交的节点.
下面在分析带环链表的特征的基础上来一一解决这些问题.
尾环链表特征分析
1.下图是尾环链表的结构。我们采用快慢指针的方法，很明显的，这是一个典型的“跑道追及问题”,俩指针进入“跑道”，速度不一样，那么俩指针必然会在某一时刻相遇。
尾环链表(摘自网络).png
因此判断链表是否有环的关键就是判断俩指针是否能相遇:
/**
* 判断是否有回环
*
* @return
*/
public boolean isLoop() {
if (isEmpty()) {
return false;
}
SNode<T> slow = headNode;
SNode<T> fast = headNode;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {//俩哥们相遇，则返回true
return true;
}
}
//如果是单链表，快指针肯定会走到结尾跳出循环
return false;
}
2.下面分析入口点问题。如下图:
尾环链表环入口分析(摘自网络).png
说明：a为头到入口的距离,x为入口到相遇点的距离,r为环长度,链表长度为L，设定环的位置以入口为原点，顺时针为正方向。这里为了更加清晰的说理，这里特殊到一般分两种情况分析:
1>环较大，俩指针在环内一周之内相遇:当slow到达入口时，fast走了2a,在环内的位置为2a-a = a,此时fast在环上顺时针领先slow距离为a，相应的slow在环上顺时针"领先"fast的距离为r-a,因为每一步fast都比slow快一步，所以再经过r-a步，fast就可以追上slow了，此时相遇时，slow共走了a+(r-a)=r步，那么在环的位置为r-a,此时有相遇点到入口的顺时针距离正好为a，与头结点到入口的距离相等;
2>环较小，快指针已经在环里浪了n(n>=1)圈才与慢指针相遇:设头结点到相遇点的距离为s,那么fast走了2s,另外fast在环里转了n圈距离为(nr + s),所以有2s = s+nr得s = nr;又有a+x=s=nr,得a + x = (n-1)r + (L - a),推出a = (n-1)*r+(L-a-x);后者为环上相遇点到入口的顺时针距离.前者代表环转圈路程，这个公式表示的现实意义为:设定俩指针，一个指针p从head出发向入口运动,另外一个指针q从相遇点出发在环内顺时针运动，一定步数后一定会在入口相遇,此结论与情况1一致。
因此问题2的实现思路为:找到相遇点，然后分配指针分别从头结点和相遇点出发向前移动，如果相遇则相遇点为入口点.代码如下:
/**
* 查找环入口
*
* @return
*/
public SNode<T> findLoopStartNode() {
if (isEmpty()) {
return null;
}
SNode<T> slow = headNode;
SNode<T> fast = headNode;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {//俩哥们相遇，则返回true
break;
}
}
if (slow == null || fast == null || fast.next == null) return null;//没有环则返回空
SNode<T> p = headNode;//从头节点出发
SNode<T> q = slow;//从相遇点出发
while (p != q) {
p = p.next;
q = q.next;
}
return p;//相遇点为环入口
}
3.有了环入口,那么环大小就好说了，从相遇点开始遍历就行:
/**
* 获取环大小
* @return
*/
public int getLoopSize() {
if (isEmpty()) {
return 0;
}
SNode<T> slow = headNode;
SNode<T> fast = headNode;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {//俩哥们相遇，则返回true
break;
}
}
if (slow == null || fast == null || fast.next == null) return 0;//没有环则返0
int size = 1;//环size从1开始
SNode<T> temp = slow.next;//从相遇点出发
while (temp != slow) {
size++;
temp = temp.next;
}
return size;
}
4.求环链表的长度:环链表的长度为环大小和入口到头节点距离的和:
/**
* 获取头节点到入口的距离
*
* @return
*/
public int getLoopEntryDistance() {
if (isEmpty()) {
return 0;
}
SNode<T> slow = headNode;
SNode<T> fast = headNode;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {//俩哥们相遇，则返回true
break;
}
}
if (slow == null || fast == null || fast.next == null) return size();//没有环则返回单链表长度
SNode<T> p = headNode;//从头节点出发
SNode<T> q = slow;//从相遇点出发
int distance = 0;
while (p != q) {
distance++;
p = p.next;
q = q.next;
}
return distance;
}
/**
* 获得带环链表大小
* @return
*/
public int getLoopLinkedListSize(){
return getLoopSize() + getLoopEntryDistance();
}
5.对面节点问题。环上距离节点最远的节点为对面节点，如图1和4、2和5、3和6为对面节点，且距离最大为环大小的一半。思路如下：判断节点是否在环上，如果在环上从当前节点前移环大小一半的步数.
对面节点问题.png
/**
* 获得对面节点
*
* @return
*/
public SNode<T> getOppositeNode(SNode<T> node) {
boolean isLoop = false;
if (isEmpty() || node == null) {
return null;
}
boolean isOnLoop = false;
//判断节点是否在环上
SNode<T> startNode = findLoopStartNode();
if (startNode == null) {//没有环，返回空
return null;
}
int loopSize = getLoopSize();
for (int i = 0; i < loopSize; i++) {
if (node == startNode) {
isOnLoop = true;
break;
}
startNode = startNode.next;
}
SNode<T> temp = node;
if (isOnLoop) {
//走环一半步数
for (int i = 0; i < loopSize / 2; i++) {
temp = temp.next;
}
}
return temp;
}
6.对于俩扩展问题，可以这样理解:加入链表A和B有交点，那么将其中一个链表首尾相连，那么另一个链表上必然会出现环，问题就转化成问题一，这里不在赘述。
总结:关于单链表，最核心的操作就是玩转节点的遍历、断开和连接操作，这四篇博客基本涵盖了单链表的大部分操作，为什么花费如此多的精力去学习它呢?因为它是基础，包含了节点操作的基本思想，熟悉了它，后面的双向链表、栈、队列就相对容易。当然，还是那句话：学习数据结构就是学习思想。一沙一世界，单链表也有很多东西可以发掘！关于单链表的学习暂时告一段落，如有纰漏欢迎指正！
