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

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

/**
 * 
 * @param head ListNode类 
 * @return bool布尔型
 */
/*********************************************************************
* 判断链表是否有环，是双指针实现，可以比喻为龟兔带跑
* 兔子相当于快指针，兔子跑的快，每次跑2步
* 乌龟相当于慢指针，乌龟跑的慢，每次跑1步
* 如果链表有环，则兔子会先于乌龟进入环，并一直在环内移动
* 等到乌龟进入环时，由于兔子跑的快，则肯定会在某时刻与乌龟相遇，即套了乌龟N圈
***********************************************************************/
bool hasCycle(struct ListNode* head ) {
    // write code here
    if(head == NULL || head->next == NULL)
        return false;
    
    struct ListNode *slow = head;
    struct ListNode *fast = head->next;//快指针如果当前如果为head时，while无法实现循环
    while(fast != slow)
    {
        //快指针每次跑2步，所以当前节点和当前的下一个节点为NULL时，说明没环
        if(fast == NULL || fast->next == NULL)
            return false;
        slow = slow->next;
        fast = fast->next->next;
    }
    return true;
}