[数据结构与算法]链表的带环问题

力扣141----判断链表中是否有环

题目描述：给你一个链表的头节点 head ，判断链表中是否有环。

解题思路：
使用快慢指针就可以了，快的走2步，慢的走1步，距离每次减1，
如果链表带环，一定可以追上。

bool hasCycle(struct ListNode *head)
{
    struct ListNode* fast=head,*slow=head;
    //fast->next要判断，这里如果链表只有一个节点，下面的走两步就会报错
    while(fast && fast->next)   
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        return true;
    }
    return false;
}

但是这题虽然比较简单，存在一些拓展问题。

力扣142—返回带环链表的入环节点

题目描述：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

解题思路：

看代码

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* fast=head,*slow=head;
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;

        if(fast==slow)
        {
            struct ListNode* meet=fast;
            while(1)       //slow和fast已经相等了，那么肯定有环了，所以死循环找。
            {
                if(meet==head)    //万一头就是入环点呢？ 所以判断一定要在走的前面
                return head;
                
                 meet=meet->next;
                head=head->next;
            }
        }
    }
    return NULL;
}