連結清單是否有環的判定，以及找到環的入口點

一、問題描述

給定一個連結清單，确定它是否有環。要求不能使用額外空間

二、解題思路

    定義一前一後兩個指針，一個跑得快（前）一個跑得慢（後）

    當跑得快的反追上慢指針，則說明有環

【問題追加】如何找打環的入口點？？？

由上思路可知，按照快指針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