1、题目

链接：141.环形链表I

2、思路

3、代码

bool hasCycle(struct ListNode *head) {
    struct ListNode*slow = head;//慢指针
    struct ListNode*fast = head;//快指针
    while(fast&&fast->next)//快指针所指向的节点和快指针的下一个节点都不为空的时候才向后执行
    {
        slow = slow->next;//慢指针一次走一步
        fast = fast->next->next;//快指针一次走两步
        if(slow==fast)//当慢指针追上快指针时停下，说明是带环链表
            return true;
    }
    return false;//慢指针没有追上快指针式 
}

4、扩展追问

扩展追问1

1、slow一次走一步，fast一次走2步，一定能追上吗？请证明。

一定能追上。

扩展追问2

2、slow一次走1步，fast一次走3步，一定能追上吗？fast一次走4步呢？n步呢？请证明。

不一定，特殊场景下可能会永远都追不上！

其它关于一次走4步和n步的推理也与上面类似。

下面再讨论一下当fast一次走4步的情况。

扩展追问3

3、请求出链表环的入口点。如果链表无环，就返回NULL。

这个追问其实也就是leetcode的第142题，下面我们来看一下它！

题目

链接：142.环形链表II

思路

两种方法：

思路1

1、公式证明

代码：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*slow = head;
    struct ListNode*fast = head;
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow==fast)
        {
            struct ListNode*meet = slow;//记录下相遇的节点
            while(meet!=head)//meet节点与head节点同时开始走，相遇点
            {
                meet = meet->next;
                head = head->next;
            }
            return meet;
        }
    }
    return NULL;
}

思路2

2、打开链表进行转化

通过上面的方法，将问题转化为求相交链表的相交节点的问题。

注意：在下面的代码中，headB就是meet->next，headA就是head，非常值得注意的一点就是在将meet->next赋值给headB之后，不要忘了把meet->next给赋值为空指针。

代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//复用的是找相加节点的代码
    struct ListNode*tailA = headA;//记录链表A的尾节点
    struct ListNode*tailB = headB;//记录链表B的尾节点
    int lenA = 1;//记录链表A的长度
    int lenB = 1;//记录链表B的长度
    while(tailA->next!=NULL)
    {
        tailA = tailA->next;
        lenA++;
    }
    while(tailB->next!=NULL)
    {
        tailB = tailB->next;
        lenB++;
    }
    
    if(tailA!=tailB)//尾节点不等，所以直接返回NULL
    {
        return NULL;
    }
    //相交，求节点，长的先走差距步，再同时走找交点
    struct ListNode*shortList = headA,*longList = headB;//默认A是较长节点的链表，B是较短的
    if(lenA>lenB)
    {
        longList = headA;
        shortList = headB;
    }
    int gap = abs(lenA - lenB);//gap存储的是节点数的差值

    while(gap--)
    {
        longList = longList->next;//节点数多的先走gap步
    }
    while(longList!=shortList)//两者同时开始进行遍历，在交点处停下
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    return longList;//随便返回一个就行，因为两个都是交点
}
struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode*slow = head;
    struct ListNode*fast = head;
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow==fast)
        {
            struct ListNode*meet = slow;//记录下相遇的节点
            struct ListNode*headB = meet->next;
            struct ListNode*headA = head;
            meet->next = NULL;
            struct ListNode*ret = getIntersectionNode(headA,headB);//返回的节点存储在ret中
            return ret;
        }
    }
    return NULL;
}