PHP实现链表的定义与反转功能示例

下面我将详细讲解“PHP实现链表的定义与反转功能示例”的完整攻略，过程中将包含两条示例说明。

什么是链表

链表是一种常见的数据结构，它由多个节点组成，每个节点存储了数据和指向下一个节点的指针。相比于数组，链表的插入和删除效率更高，但访问操作的效率较低。

PHP实现链表的定义

在PHP中，我们可以使用类来实现链表。首先，我们需要定义一个节点类，代码如下：

class ListNode {
    public $val; // 当前节点的值
    public $next; // 指向下一个节点的指针

    public function __construct($val = 0, $next = null) {
        $this->val  = $val;
        $this->next = $next;
    }
}

接下来，我们可以定义整个链表的类，代码如下：

class LinkedList {
    private $dummyHead; // 虚拟头节点
    private $size; // 链表长度

    public function __construct() {
        $this->dummyHead = new ListNode();
        $this->size      = 0;
    }

    // 获取链表中的元素个数
    public function getSize() {
        return $this->size;
    }

    // 判断链表是否为空
    public function isEmpty() {
        return $this->size == 0;
    }

    // 在链表的第index个位置添加新的元素e
    public function add($index, $e) {
        if ($index < 0 || $index > $this->size) {
            throw new InvalidArgumentException('Add failed. Index is invalid.');
        }

        $prev = $this->dummyHead;
        for ($i = 0; $i < $index; $i++) {
            $prev = $prev->next;
        }

        $prev->next = new ListNode($e, $prev->next);
        $this->size++;
    }

    // 在链表头添加新的元素e
    public function addFirst($e) {
        $this->add(0, $e);
    }

    // 在链表末尾添加新的元素e
    public function addLast($e) {
        $this->add($this->size, $e);
    }

    // 获取链表的第index个位置的元素
    public function get($index) {
        if ($index < 0 || $index >= $this->size) {
            throw new InvalidArgumentException('Get failed. Index is invalid.');
        }

        $cur = $this->dummyHead->next;
        for ($i = 0; $i < $index; $i++) {
            $cur = $cur->next;
        }

        return $cur->val;
    }

    // 获取链表的第一个元素
    public function getFirst() {
        return $this->get(0);
    }

    // 获取链表的最后一个元素
    public function getLast() {
        return $this->get($this->size - 1);
    }

    // 修改链表的第index个位置的元素为e
    public function set($index, $e) {
        if ($index < 0 || $index >= $this->size) {
            throw new InvalidArgumentException('Set failed. Index is invalid.');
        }

        $cur = $this->dummyHead->next;
        for ($i = 0; $i < $index; $i++) {
            $cur = $cur->next;
        }

        $cur->val = $e;
    }

    // 查找链表中是否存在元素e
    public function contains($e) {
        $cur = $this->dummyHead->next;
        while ($cur != null) {
            if ($cur->val == $e) {
                return true;
            }
            $cur = $cur->next;
        }

        return false;
    }

    // 从链表中删除第index个元素，返回删除的元素
    public function remove($index) {
        if ($index < 0 || $index >= $this->size) {
            throw new InvalidArgumentException('Remove failed. Index is invalid.');
        }

        $prev = $this->dummyHead;
        for ($i = 0; $i < $index; $i++) {
            $prev = $prev->next;
        }

        $ret         = $prev->next;
        $prev->next  = $ret->next;
        $ret->next   = null; // 方便回收内存
        $this->size--;

        return $ret->val;
    }

    // 从链表中删除第一个元素，返回删除的元素
    public function removeFirst() {
        return $this->remove(0);
    }

    // 从链表中删除最后一个元素，返回删除的元素
    public function removeLast() {
        return $this->remove($this->size - 1);
    }

    // 删除链表中值为e的元素
    public function removeElement($e) {
        $prev = $this->dummyHead;
        while ($prev->next != null) {
            if ($prev->next->val == $e) {
                $delNode     = $prev->next;
                $prev->next  = $delNode->next;
                $delNode->next = null; // 方便回收内存
                $this->size--;
            } else {
                $prev = $prev->next;
            }
        }
    }

    // 反转链表
    public function reverse() {
        $prev = null;
        $curr = $this->dummyHead->next;
        while ($curr != null) {
            $next        = $curr->next;
            $curr->next  = $prev;
            $prev        = $curr;
            $curr        = $next;
        }

        $this->dummyHead->next = $prev;
    }

    // 打印链表
    public function __toString() {
        $sb  = '';
        $cur = $this->dummyHead->next;
        while ($cur != null) {
            $sb .= $cur->val . '->';
            $cur = $cur->next;
        }
        $sb .= 'NULL';

        return $sb;
    }
}

PHP实现链表反转的示例

接下来，我将演示如何使用上面实现的链表类进行反转操作。

示例一

$list = new LinkedList();
$list->addLast(1);
$list->addLast(2);
$list->addLast(3);
$list->addLast(4);
echo $list . PHP_EOL;

// 反转链表
$list->reverse();
echo $list . PHP_EOL;

输出结果：

1->2->3->4->NULL
4->3->2->1->NULL

示例二

$list = new LinkedList();
$list->addLast('a');
$list->addLast('b');
$list->addLast('c');
$list->addLast('d');
$list->addLast('e');
echo $list . PHP_EOL;

// 反转链表
$list->reverse();
echo $list . PHP_EOL;

输出结果：

a->b->c->d->e->NULL
e->d->c->b->a->NULL

以上就是如何在PHP中实现链表的定义和反转操作的完整攻略，希望对你有所帮助。