札记之PHP实现链表中环的检测

思路：定义两个一快一慢指针，快指针每次移动两个节点，慢指针每次移动一个节点，如果相遇则说明存在环，如果快指针最后指向了NULL，则说明不存在环；

代码实现

札记之PHP实现判断一个单链表是否为回文链表

class ListNode
{
    private $data = NULL;
    private $next = NULL;

    public function __construct($data = NULL) {
        $this->data = $data;
    }
    public function __get($var)
    {
        return $this->$var;
    }
    public function __set($var, $val)
    {
        return $this->$var = $val;
    }
}

class LinkedList
{
    private $head = NULL;
    private $currentNode = NULL;
    private $length = 0;

    public function insert($data = NULL) 
    {
        $newNode = new ListNode($data);
        if ($this->head == NULL) {
            $this->head = &$newNode;
        } else {
            $currentNode = $this->head;
            while ($currentNode->next !== $this->head) {
                $currentNode = $currentNode->next;
            }
            $currentNode->next = $newNode;
            $newNode->next = $this->head;
        }
        $newNode->next = $this->head;
    }

    public function display()
    {
        $currentNode = $this->head;
        while ($currentNode->next != $this->head) {
            echo $currentNode->next->data . PHP_EOL;
            $currentNode = $currentNode->next;
        }
    }

    public function checkCircle()
    {
        $currentNode = $this->head;
        if (NULL == $currentNode || NULL == $currentNode->next) {
            return false;
        }

        $slow = $currentNode->next;
        $fast = $currentNode->next;
        
        while ($fast != NULL && $fast->next != NULL) {
            $fast = $fast->next->next;
            $slow = $slow->next;
            if ($fast === $slow) {
                return true;
            }
        }
        return false;
    }
}
$list = new LinkedList();
$list->insert(1);
$list->insert(2);
$list->insert(3);
$list->display();
var_dump($list->checkCircle());

运行结果

2
3
/Users/jiayuan/tree/isCrlinked.php:78:
bool(true)

参考资料：

• 快指针与慢指针之间差一步。此时继续往后走，慢指针前进一步，快指针前进两步，两者相遇。
• 快指针与慢指针之间差两步。此时唏嘘往后走，慢指针前进一步，快指针前进两步，两者之间相差一步，转化为第一种情况。
• 快指针与慢指针之间差N步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差(N+1-2)->N-1步。因此，此题得证。所以快指针必然与慢指针相遇。又因为快指针速度是慢指针的两倍，所以相遇时必然只绕了一圈。

为什么快慢指针一定能相遇，点击参考