判断链表是否有环

有一个单向链表，链表中有可能出现“环”，就像下图这样。
那么，如何用程序来判断该链表是否为有环链表呢？

image.png

首先创建两个指针p1和p2（在Java里就是两个对象引用），让它们同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针p1每次向后移动1个节点，让指针p2每次向后移动2个节点，然后比较两个指针指向的节点是否相同。如果相同，则可以判断出链表有环，如果不同，则继续下一次循环。
第1步，p1和p2都指向节点5。

image.png
第2步，p1指向节点3，p2指向节点7。
image.png
第3步，p1指向节点7，p2指向节点6。
image.png

第4步，p1指向节点2，p2指向节点1。

image.png
第5步，p1指向节点6，p2也指向节点6，p1和p2所指相同，说明链表有环。
image.png

具体代码实现：

<?php
/**
 * 
 */
class Node{

    private $data;
    private $next;

    public function __construct($data){
        $this->data = $data;
    }

    public function __set($property_name,$value){
        $this->$property_name = $value;
    }

    public function __get($property_name){
        return $this->$property_name;
    }

}
class Code{

    function isCycle($node){
        $p1 = $node;
        $p2 = $node;
        while ($p2 != null && $p2->next != null) {
            $p1 = $p1->next;
            $p2 = $p2->next->next;
            if($p1 == $p2){
                return true;
            }
        }
        return false;
    }

    //运行
    function run(){
        $node1 = new Node(5);
        $node2 = new Node(3);
        $node3 = new Node(7);
        $node4 = new Node(2);
        $node5 = new Node(6);
        $node6 = new Node(8);
        $node7 = new Node(1);
        $node1->next = $node2;
        $node2->next = $node3;
        $node3->next = $node4;
        $node4->next = $node5;
        $node5->next = $node6;
        $node6->next = $node7;
        $node7->next = $node4;

        var_dump($this->isCycle($node1));
    }
    
}
$obj = new Code();
$obj->run();

输出结果：

image.png