札记之PHP实现找出链表的中间结点

题目：给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3
返回的结点值为 3

思路：定义两个一快一慢指针，快指针每次移动两个节点，慢指针每次移动一个节点，快指针到终点指向了NULL，慢指针正好到中间；

代码实现

class ListNode
{
    private $data;
    private $next;
    public function __construct(string $data)
    {
        $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 $length = 0;
    private $currentNode;

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

    public function findMidNode()
    {
        if ($this->head == NULL || $this->head->next == NULL) {
            return false;
        }
        $slow = $this->head;
        $fast = $this->head;

        while ($fast != NULL && $fast->next != NULL) {
            $fast = $fast->next->next;
            $slow = $slow->next;
        }
        return $slow;
    }
}

$linkedObj = new LinkedList();
$linkedObj->insert(1);
$linkedObj->insert(2);
$linkedObj->insert(3);
$linkedObj->insert(4);
$linkedObj->insert(5);

$obj = $linkedObj->findMidNode();
var_dump($obj->data);

运行结果

string(1) "3"