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

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

/**
 * 
 * @param head ListNode类 
 * @return bool布尔型
 */
// 这是一种比较取巧的方式，因为题目中有限定范围，可以拿最大范围做比较
bool hasCycle(struct ListNode* head ) {

    if (NULL == head)
    {
        return false;
    }
    int num = 0;
    // 链表正常变量结束 或 num数量加到1000 退出循环 
    while (NULL != head && num <= 10000)
    {
        head = head->next;
        ++num;
    }
    // 有环则会死循环，一直加加num，最后超过10000跳出
    if(num > 10000)
        return true;
    return false;
}

// 这是一种比较通用的方式，如果有环，快慢指针一定会汇集到一起
bool hasCycle(struct ListNode* head ) {
    if (NULL == head)
    {
        return false;
    }
    // 走一步的指针
    struct ListNode* ptList_1 = head;
    // 走两边的指针
    struct ListNode* ptList_2 = head;

    // 如果没有环，那走两步的指针肯定会先到达队尾，能到达队尾并跳出循环，证明无环
    while (NULL != ptList_2 && NULL != ptList_2->next)
    {
        ptList_1 = ptList_1->next;
        ptList_2 = ptList_2->next->next;

        // 如果有环，快慢指针一定会汇集到一起
        if(ptList_1 == ptList_2)
            return true;
    }
    return false;
}