利用PHP实现递归删除链表元素的方法示例

<?php
require 'ArrayRecursion.php';
/
  递归实现数组求和
 /
$arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
echo ArrayRecursion::recursionSum($arr);

<?php
/
  使用递归对数组求和 方便对递归的理解
  Class ArrayRecursion
 /
class ArrayRecursion
{
  public static function sum(array $arr) {
    return self::recursionSum($arr);
  }
  public static function recursionSum(array $arr, $i = 0) {
    if (count($arr) == $i) {
      return 0;
    }
    return $arr[$i] + self::recursionSum($arr, $i + 1);
  }
}

<?php
require 'LinkedList.php';
require 'LinkedListRecursion.php';
/
  实例化一个链表，向链表中添加50个元素
 /
$linkedList = new LinkedList();
for ($i = 0; $i < 50; $i++) {
  if ($i % 7 == 0) {
    $linkedList->addFirst(99);
  } else {
    $linkedList->addFirst($i);
  }
}
echo $linkedList->toString();
/打印链表中元素
  99->48->47->46->45->44->43->99->41->40->39->
  38->37->36->99->34->33->32->31->30->29->99->27->
  26->25->24->23->22->99->20->19->18->17->16->15->
  99->13->12->11->10->9->8->99->6->5->4->3->2->1->99->null
 /
//将链表对象传入一个能删除指定元素的方法，如 99
echo LinkedListRecursion::deleteElement($linkedList, 99)->toString();
/打印
  48->47->46->45->44->43->41->40->
  39->38->37->36->34->33->32->31->
  30->29->27->26->25->24->23->22->
  20->19->18->17->16->15->13->12->
  11->10->9->8->6->5->4->3->2->1->null
 /

<?php
/
  链表的实现
  Class LinkedList
 /
class LinkedList
{
  private $dummyHead;
  private $size;
  /
    初始化链表 null->null
    LinkedList constructor.
   /
  public function __construct() {
    $this->dummyHead = new Node(null, null);
    $this->size = 0;
  }
  /
    获取链表大小
    @return int
   /
  public function getSize(): int {
    return $this->size;
  }
  /
    判断链表是否为空
    @return bool
   /
  public function isEmpty(): bool {
    return $this->size == 0;
  }
  /
    在链表的第 index 位置添加元素
    @param int $index
    @param $e
   /
  public function add(int $index, $e): void {
    if ($index < 0 || $index > $this->size) {
      echo "索引范围错误";
      exit;
    }
    $prve = $this->dummyHead;
    for ($i = 0; $i < $index; $i++) {
      $prve = $prve->next;
    }
    //将上插入位置的上一个位置的 next 节点指向插入节点，插入节点的 next 节点信息指向原上节点的 next 节点
    $prve->next = new Node($e, $prve->next);
    $this->size++;
  }
  /
    向链表开头添加元素
    @param $e
   /
  public function addFirst($e): void {
    $this->add(0, $e);
  }
  /
    向链表末尾添加元素
    @param $e
   /
  public function addLast($e): void {
    $this->add($this->size, $e);
  }
  /
    获取链表第 index 位置元素
    @param $index
   /
  public function get($index) {
    if ($index < 0 || $index > $this->size) {
      echo "索引范围错误";
      exit;
    }
    $node = $this->dummyHead;
    for ($i = 0; $i < $index + 1; $i++) {
      $node = $node->next;
    }
    return $node->e;
  }
  /
    获取链表第一个元素
    @return mixed
   /
  public function getFirst() {
    return $this->get(0);
  }
  /
    获取链表一个元素
    @return mixed
   /
  public function getLast() {
    return $this->get($this->size - 1);
  }
  /
    修改链表中第 index 位置元素值
    @param $index
    @param $e
   /
  public function update($index, $e) {
    if ($index < 0 || $index > $this->size) {
      echo "索引范围错误";
      exit;
    }
    $node = $this->dummyHead;
    for ($i = 0; $i < $index + 1; $i++) {
      $node = $node->next;
    }
    $node->e = $e;
  }
  /
    判断链表中是否存在某个元素
    @param $e
    @return bool
   /
  public function contains($e): bool {
    for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {
      if ($node->e == $e) {
        return true;
      }
    }
    return true;
  }
  /
    删除链表中第 index 位置元素
    @param $index
   /
  public function remove($index) {
    if ($index < 0 || $index > $this->size) {
      echo "索引范围错误";
      exit;
    }
    if ($this->size == 0) {
      echo "链表已经是空";
      exit;
    }
    $prve = $this->dummyHead;
    for ($i = 0; $i < $index; $i++) {
      $prve = $prve->next;
    }
    $node = $prve->next;
    $prve->next = $node->next;
    $this->size--;
    return $node->e;
  }
  /
    删除链表头元素
   /
  public function removeFirst() {
    return $this->remove(0);
  }
  /
    删除链表末尾元素
   /
  public function removeLast() {
    return $this->remove($this->size - 1);
  }
  /
    获取头结点信息
    @return mixed
   /
  public function getHead() {
    return $this->dummyHead->next;
  }
  /
    设置头
    @param Node $head
   /
  public function setHead(Node $head) {
    $this->dummyHead->next = $head;
  }
  /
    链表元素转化为字符串显示
    @return string
   /
  public function toString(): string {
    $str = "";
    for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {
      $str .= $node->e . "->";
    }
    return $str . "null";
  }
}
class Node
{
  public $e;//节点元素
  public $next; //下个节点信息
  /
    构造函数 设置节点信息
    Node constructor.
    @param $e
    @param $next
   /
  public function __construct($e, $next) {
    $this->e = $e;
    $this->next = $next;
  }
}

<?php
/
  递归删除链表指定元素
  Class LinkedListRecursion
 /
class LinkedListRecursion
{
  public static function deleteElement(LinkedList $linkedList, $val) {
    $linkedList->setHead(self::recursionDelete($linkedList->getHead(), $val));
    return $linkedList;
  }
  
   /
    递归函数 递归删除链表元素
    @param $head
    @param $val
    @return null
   /
  private static function recursionDelete($head, $val) {
    if ($head == null) {
      return null;
    } else {
      if ($head->e == $val) {
        return self::recursionDelete($head->next, $val);
      } else {
        $head->next = self::recursionDelete($head->next, $val);
        return $head;
      }
    }
  }
}