算法应用-单链表

单向链表中代码实现检查是否有环，如果有环，求环的长度和入环的节点？

思路：

有环单链表.png

1. 假设单链表如上图，检查是否有环这个简单，设置快慢指针（即快指针一次走2步，慢指针一次走1步），如果是有环的链表，则快指针最终会与慢指针相遇。
2. 求环的长度？在上一步的基础上，如图，假设一个相遇点，此时令快指针不动，慢指针继续走，并开始计步，当再次走到相遇点时慢指针走了一圈，走的步数就是环的长度。
3. 求入环的节点？如图就是求X步。 首先与求是否有环一样的做法，然后在达到相遇点时，假设环的长度为C，快指针走了N2圈，慢指针走了N1圈，则：（X+Y + N1*C）*2 = X + Y + N2*C;
   得出： X = (N2 - N1)*C - Y;
   然后因为 C = Y+Z; 综合可得：

• X = (N2 - N1 -1) *C +Z;
  我们令快指针从第一个节点开始，一次走一步， 走X步时, 达到入环节点;
  同时,慢指针从相遇点开始向前走，当走了X步时，因为X=(N2 - N1 -1)*C +Z，所以是走了(N2 - N1 -1)圈后再往前走Z步，它到达的位置也会是入环点。
  由上可知，当快慢指针再次相遇时的节点就是入环节点。
  代码如下:

typedef struct LinkNode{
    char *data;
    struct LinkNode *next;
}LinkNode;

void testLinkList(LinkNode *linkList){
    
    // 1. 快慢指针会相遇则说明有环，快指针到了null的位置，则说明没有环。
    LinkNode *slow = linkList->next;
    LinkNode *fast = slow->next;
    
    while (fast && slow != fast) {
        slow = slow->next;
        fast = fast->next ? fast->next->next : NULL;
    }
    
    if (fast) {
        printf("该链表有环");
        
        int circleLen = 1;
        slow = slow->next;
        while (slow != fast) {
            circleLen++;
            slow = slow->next;
        }
        printf("链表中环的长度为：%d", circleLen);
        
        // 寻找入环节点
        fast = linkList;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        printf("链表入环的节点为：%p", fast);
    }
}