php实现环形链表

环形链表的实现原理

环形链表是一种特殊的链表数据结构，其最后一个节点的指针不是指向null，而是指向链表中的某个节点（通常是头节点），形成一个闭环。这种结构常用于实现循环队列、轮询调度等场景。

PHP实现环形链表的基本结构

class ListNode {
    public $data;
    public $next;

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

class CircularLinkedList {
    private $head;

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

插入节点到环形链表

public function insert($data) {
    $newNode = new ListNode($data);

    if ($this->head === null) {
        $this->head = $newNode;
        $newNode->next = $this->head;
        return;
    }

    $current = $this->head;
    while ($current->next !== $this->head) {
        $current = $current->next;
    }

    $current->next = $newNode;
    $newNode->next = $this->head;
}

删除环形链表中的节点

public function delete($key) {
    if ($this->head === null) {
        return;
    }

    $current = $this->head;
    $prev = null;

    do {
        if ($current->data === $key) {
            if ($prev !== null) {
                $prev->next = $current->next;
                if ($current === $this->head) {
                    $this->head = $current->next;
                }
            } else {
                if ($current->next === $this->head) {
                    $this->head = null;
                } else {
                    $prev = $this->head;
                    while ($prev->next !== $this->head) {
                        $prev = $prev->next;
                    }
                    $this->head = $current->next;
                    $prev->next = $this->head;
                }
            }
            return;
        }
        $prev = $current;
        $current = $current->next;
    } while ($current !== $this->head);
}

遍历环形链表

public function display() {
    if ($this->head === null) {
        echo "List is empty\n";
        return;
    }

    $current = $this->head;
    do {
        echo $current->data . " ";
        $current = $current->next;
    } while ($current !== $this->head);
    echo "\n";
}

检测环形链表

public function isCircular() {
    if ($this->head === null) {
        return true;
    }

    $slow = $this->head;
    $fast = $this->head;

    while ($fast !== null && $fast->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;

        if ($slow === $fast) {
            return true;
        }
    }
    return false;
}

使用示例

$list = new CircularLinkedList();
$list->insert(1);
$list->insert(2);
$list->insert(3);
$list->display(); // 输出: 1 2 3

$list->delete(2);
$list->display(); // 输出: 1 3

echo $list->isCircular() ? "是环形链表" : "不是环形链表";

实现注意事项

环形链表的实现需要注意边界条件处理，特别是空链表和单节点链表的情况。所有操作都应维护环形结构，确保最后一个节点始终指向头节点。删除操作需要特别处理头节点的删除情况。

对于大规模数据操作，环形链表的遍历操作需要谨慎，避免无限循环。可以使用计数器或设置最大迭代次数来防止这种情况发生。