1. 判断链表是否成环

通过快慢指针可以解决这个问题。

设置两个指针 ptrFast 和 ptrSlow ，Fast指针一次走两步，Slow指针一次走一步。可以想象，如果链表有环的话，那么Fast一定先进环Slow后进环（特殊情况，链表首尾相连成环）。

现在只考虑环内的视野，可以想象，当Slow也进入环内的时候，不管Fast此时在环内的任何位置，两个指针按照原来的步频继续前进，最终一定会相遇，因为步频相差1，即每移动一次两个指针距离缩短1，所以最终一定会相遇。

转换成代码就是让两个指针无限前进，如果Fast探测到NULL了说明无环，如果最终两个指针相遇则有环。

// 判断是否有环
int hasCircle(ListNode* head) {
    ListNode* ptrFast = head;
    ListNode* ptrSlow = head;

    do
    {
        if (ptrFast->next == NULL)
            return 0;
        else if (ptrFast->next->next == NULL)
            return 0;

        ptrFast = ptrFast->next->next;
        ptrSlow = ptrSlow->next;
    } while (ptrFast != ptrSlow);
    return 1;
}

2. 找出环入口

这里先来一个结论：当Slow进入环内，两个指针开始追赶，当两个指针相遇时Slow指针一定没有走完环的一圈，这个很好证明。

然后看下图：

设链表头到环入口距离为a，环入口到相遇点距离为b，相遇点到环入口距离为c，环长为L，假设两指针相遇时Fast已经在环内走了x圈+b的路程即xL+b。
所以可以得到Slow指针走过的路程为a+b，Fast指针走过的路程为a+xL+b。

Fast的速度为Slow的速度的两倍，所以现有：
(a + b) * 2 = a + xL + b
得 a + b = xL
得 a = (x-1)L + L - b
得 a = (x-1)L + c

最后这个式子是什么意思呢，即a的距离等于c的距离加若干圈环得长度。那这又是什么意思呢？用代码来说就是，现在再来两个指针，一个从链表头开始走，一个从相遇点顺着链表走，最终一定会在环入口相遇！

// 寻找环入口
// 输入有环链表
ListNode* findCircleEntry(ListNode* head) {
    ListNode* ptrFast = head;
    ListNode* ptrSlow = head;

    // 寻找相交节点
    do
    {
        ptrFast = ptrFast->next->next;
        ptrSlow = ptrSlow->next;
    } while (ptrFast != ptrSlow);

    // 寻找环入口
    // 这时指针不分快慢，每次都走一步
    // 一个指针到链表入口，一个指针停留在相交位置
    ptrSlow = head;
    while (ptrSlow != ptrFast) {
        ptrSlow = ptrSlow->next;
        ptrFast = ptrFast->next;
    }

    // 此时的相交节点即为环入口
    return ptrSlow;
}

3. 代码汇总

#include "LinkedList.h"

// 判断是否有环
int hasCircle(ListNode* head) {
    ListNode* ptrFast = head;
    ListNode* ptrSlow = head;

    do
    {
        if (ptrFast->next == NULL)
            return 0;
        else if (ptrFast->next->next == NULL)
            return 0;

        ptrFast = ptrFast->next->next;
        ptrSlow = ptrSlow->next;
    } while (ptrFast != ptrSlow);
    return 1;
}

// 寻找环入口
// 输入有环链表
ListNode* findCircleEntry(ListNode* head) {
    ListNode* ptrFast = head;
    ListNode* ptrSlow = head;

    // 寻找相交节点
    do
    {
        ptrFast = ptrFast->next->next;
        ptrSlow = ptrSlow->next;
    } while (ptrFast != ptrSlow);

    // 寻找环入口
    // 这时指针不分快慢，每次都走一步
    // 一个指针到链表入口，一个指针停留在相交位置
    ptrSlow = head;
    while (ptrSlow != ptrFast) {
        ptrSlow = ptrSlow->next;
        ptrFast = ptrFast->next;
    }

    // 此时的相交节点即为环入口
    return ptrSlow;
}

int main() {
    // 建立链表
    ListNode* head;
    ListInit(&head);
    ListPushBack(&head, 1);
    ListPushBack(&head, 2);
    ListPushBack(&head, 3);
    ListPushBack(&head, 4);
    ListPushBack(&head, 5);
    ListPushBack(&head, 6);
    ListPushBack(&head, 7);
    print_linkedList(head);
    printf("%d\n", hasCircle(head));

    // 成环
    ListNode* ptr = head;
    ListNode* tmp = NULL;
    while (ptr->next) {
        if (ptr->data == 3)
            tmp = ptr;
        ptr = ptr->next;
    }
    ptr->next = tmp;
    printf("%d\n", hasCircle(head));

    int res = findCircleEntry(head)->data;
    printf("相交节点：%d\n", res);

    system("pause");
    return 0;
}

4. 扩展问题：判断两个链表是否相交（链表可能带环）

这个问题可以分为上面6种情况，现在要做的就是区分这6种情况。

首先，判断两个链表是否带环，如果都不带环，则是1或2。
所以下面就是判断两个无环链表是否相交，方法很简单。先分别算出两个链表的长度，然后让长链表的指针先往前走两个链表长度之差的步数，可以想到对于情况2来说，这时候两个子链表已经等长了，所以现在让两个指针一起往前走，如果链表相交则指针必相交，如果链表不相交则指针也永远不会相交。

然后，如果一个链表无环一个链表有环，即情况3，可以想到两链表必不相交。

然后就是两个链表都带环的情况了，这时候找两个链表的环入口，如果环入口相同，即情况5，则链表相交。

最后就是区分情况4和情况6。分别记录两个不同的环入口，然后让一个指针从其中一个环入口开始往后走，如果是情况6则这个指针必会遇到另一个环入口，如果走了一圈还没遇到另一个环入口那就是情况4。