问题：
- 判断单链表是否有环；
- 若有环，找出环的入口节点；
- 若有环，求出环上节点的个数；
- 若有环，求出整个链表的节点的个数；
1. 判断是否有环，并取入口节点
1.1 用HashSet来解决
public ListNode EntryNodeOfLoop(ListNode pHead){
HashSet<ListNode> hs = new HashSet<ListNode>();
while(pHead!=null){
if(!hs.add(pHead))//如果包含了，那么这个就是入口结点
return pHead;
pHead = pHead.next;
}
return null;
}
1.2 计算循环
用两个指针，一个fast指针，每次走两步，一个slow指针，每次走一步，当fast指针与slow指针相遇时，假设fast指针走了2x，那么slow指针走了x，由于有环，那么为了便于理解，分为两种情况：
- 情况一，fast指针只比slow指针多走一个环
第一次相遇的时：
这个时候将fast 重新赋值为开头：
再走两次，则找到了环的入口结点：
解题思路:
- 找环中相汇点。分别用fast，slow指向链表头部，slow每次走一步，fast每次走二步，直到fast==slow找到在环中的相汇点。
- 找环的入口。接上步，当fast==slow时，fast所经过节点数为2x,slow所经过节点数为x,设环中有n个节点，fast比slow多走一圈有2x=n+x; n=x;
可以看出slow实际走了一个环的步数，再让fast指向链表头部，slow位置不变。假设链表开头到环接口的距离是y，如下图所示，那么x-y表示slow指针走过的除链表开头y在环中走过的距离，那么slow再走y步，此时fast结点与slow结点相遇，fast == slow ，x-y+y=x = n，即此时slow指向环的入口。
- 情况二，当fast比slow 多走n个环
解题思路
- 找环中相汇点。分别用fast，slow指向链表头部，slow每次走一步，fast每次走二步，直到fast==slow找到在环中的相汇点。
- 找环的入口。接上步，当fast==slow时，fast所经过节点数为2x,slow所经过节点数为x,设环中有n个节点，fast比slow多走r圈有2x=rn+x; x=rn;（r为圈数，n为一圈的结点数）
可以看出slow实际走了多个环的步数，再让fast指向链表头部，slow位置不变。假设链表开头到环接口的距离是y，那么x-y表示slow指针走过的除链表开头y在环中走过的距离，那么slow再走y步，此时fast结点与slow结点相遇，fast == slow ，x-y+y=x = rn，即此时slow指向环的入口。
基于上面上中情况的总结，代码实现如下：
public ListNode EntryNodeOfLoop2(ListNode pHead){
ListNode fast = pHead;
ListNode slow = pHead;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){ // 当 fast 与 slow 相遇，则有环
fast = pHead;
while(fast != slow){ // 修改fast指向，再次相遇时，则取到入口节点
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null; // 否则，无环！
}
2. 若有环，求环上节点的个数
若有环，则记录相遇节点存入临时变量tempPtr，并让slow(或者fast，都一样)继续向前走：
slow = slow -> next；
slow == tempPtr;
此时经过的步数就是环上节点的个数，完整代码：
typedef struct node {
char data ;
node * next ;
} Node;
int lenngthOfLoop(Node *head) {
int tmp=0;
Node *fast, *slow,*tempPtr;
slow = head ;
fast = head ;
while (slow != NULL && fast != NULL && fast -> next != NULL)
{
slow = slow -> next ;
fast = fast -> next -> next ;
if (slow == fast)
break ;
}
if (slow != fast)
return 0 ;
tempPtr= slow;
while (slow!=tempPtr )
{
slow = slow -> next ;
tmp++;
}
return tmp;
}
2. 若有环，求整个链表的长度：
链表长度L = 起点到入口点的距离 + 环的长度n 。
原文地址：
https://www.cnblogs.com/fankongkong/p/7007869.html
https://blog.csdn.net/weixin_42078660/article/details/89265288
网友评论