题解 | #判断链表中是否有环#

#include <stdbool.h>
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param head ListNode类 
 * @return bool布尔型
 */
/*
解题思路：
当单向链表出现环路时，一定会相遇；
证明如下：
可以将这个题目抽象为高中时的相遇问题，slow和fast都从一个起点出发，但是他们速度不一样。
那么题目就可以替换为：slow和fast从一个起点出发，设从一个节点移到下一个节点的距离为1M,环路节点的距离为xm循环一次，从起点到达环路起始点的距离为y m，slot速度为1，fast速度为2（实际上速度为多少都是回相遇的只要有环路）。
 起点               __________________________
|——————————————————|		环路 x m  		|
	y m 			——————————————————————————
	相遇即两者路程差为环路的k倍
	设ts相遇
	所以方程式为：（2*t-y）-（t-y）=kx
	t=kx   --->总有ts的时候相遇了
*/
/*
问题归纳：
1、还是没有对只有一个节点链表的情况考虑充分。
2、fast->next->next!=NULL只能判断fast->next->next为不为空，fast->next->next=NULL不等于fast->next=NULL，反过来也是的。
*/


bool hasCycle(struct ListNode* head ) {
    // write code here
    struct ListNode* slow=head;
    struct ListNode* fast=head;
    if(head!=NULL)//链表不为空
    {
        while(fast->next!=NULL&&fast->next->next!=NULL)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast)
            {
                return true;
            }
        }

    }
    return false;
}