有环单链表的相关问题

问题：

1. 判断单链表是否有环；
2. 若有环，找出环的入口节点；
3. 若有环，求出环上节点的个数；
4. 若有环，求出整个链表的节点的个数；

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 重新赋值为开头：

再走两次，则找到了环的入口结点：

解题思路:

1. 找环中相汇点。分别用fast，slow指向链表头部，slow每次走一步，fast每次走二步，直到fast==slow找到在环中的相汇点。
2. 找环的入口。接上步，当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个环

解题思路

1. 找环中相汇点。分别用fast，slow指向链表头部，slow每次走一步，fast每次走二步，直到fast==slow找到在环中的相汇点。
2. 找环的入口。接上步，当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