链表是否有环的判定，以及找到环的入口点

一、问题描述

给定一个链表，确定它是否有环。要求不能使用额外空间

二、解题思路

    定义一前一后两个指针，一个跑得快（前）一个跑得慢（后）

    当跑得快的反追上慢指针，则说明有环

【问题追加】如何找打环的入口点？？？

由上思路可知，按照快指针p2每次走两步，慢指针p1每次走一步的方式走，发现p1和p2重合，就确定了单向链表有环路了。接下来，让p2回到链表头部，重新走，每次步长不是走2步了，而是走1步，那么当p1和p2再次相遇的时候，就是环路的入口了。

三、算法代码

/**********************************************
Author:tmw
date:2018-4-14
**********************************************/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct listnode
{
    int data;
    struct listnode* next;
}listnode;

bool hasCycle( listnode* head )
{
    /**函数入口判断：链表为空即不进入算法**/
    if( head == NULL )
        return false;

    listnode* fast = head;
    listnode* slow = head->next;

    /**fast指针没追上slow指针则执行下步**/
    while( fast != slow )
    {
        /**当fast指针没追slow指针反而指空了，说明没有环**/
        if( fast == NULL || fast->next == NULL )
            return false;

        /**slow指针一步一步移**/
        slow = slow->next;

        /**fast指针胯步移**/
        fast = fast->next->next;
    }
    return true;
}
           

四、测试代码及结果

leetcode accept