如何判断一个单链表是否有环

用一个简单的办法去解决：快慢指针

如果有环有下面2种情况：

图1 图2

图1 快慢指针过程

fast->2->4->6->3->5
slow->1->2->3->4->5

变成代码

function isCheckRings($head)
{
    $fast = $head;
    $slow = $head;

    while ($fast !== null && $fast->next !== null) {
        $fast = $fast->next->next;
        $slow = $slow->next;
        if ($fast === $slow) {
            return true;
        }
    }
    return false;
}

查找环入口

先判断单链表是否有环，让快指针变成每次走一步，当快慢指针在次相遇，也就是环入口了。

变成代码

function findRings($head)
{
    $fast = $head;
    $slow = $head;

    // 先判断是否有环
    while ($fast != null && $fast->next !== null) {
        $fast = $fast->next->next;
        $slow = $slow->next;
        if ($fast === $slow) {
            break;
        }
    }
    if ($fast === null || $fast->next === null) {
        return false;
    }

    $fast = $head;
    while ($fast !== $slow) {
        $fast = $fast->next;
        $slow = $slow->next;
    }
    return $fast->data;
}