PHP 按循环单链表的键删除最后一个节点

 PHP 数据结构

在此方法中，删除循环单链表中具有指定键（值）的最后一个节点。例如 - 如果给定列表为 10->20->30->20->40 并且删除最后一次出现的 20，则列表将变为 10->20->30->40。

如果循环的头部单向链表不为空，创建三个节点: 1. lastNode - 跟踪 value 等于 key 的最后一个节点， 2. previousToLast - 跟踪 lastNode 之前的节点和 3. temp - 遍历列表。然后遍历列表到末尾，同时每当找到值等于指定键的节点时更新 lastNode 和 previousToLast。最后删除lastNode并相应地更新链接。

函数pop_last就是为此目的而创建的。这是一个3步过程。

public function pop_last($key) {       

  //1.如果 head 不为空，则创建三个节点
  //lastNode - 跟踪具有值的最后一个节点
  // 等于 key，previousToLast - 跟踪
  //lastNode 之前的节点，temp - 到
  //遍历列表
  if($this->head != null) {
    $temp = new Node();
    $previousToLast = null;
    $lastNode = null;
    
    //2。遍历列表并不断更新
    // 每当找到一个节点时，lastNode 和 previousToLast
    // 值等于指定的键
    if($this->head->data == $key) 
      $lastNode = $this->head;
    
    $temp = $this->head;
    while($temp->next != $this->head) {
      if($temp->next->data == $key) {
        $previousToLast = $temp;
        $lastNode = $temp->next;
      }
      $temp = $temp->next;
    }
 
    //3。删除lastNode并更新所有链接
    if($lastNode != null) {
      if($lastNode == $this->head) {
        if($this->head->next == $this->head)
          $this->head = null;
        else
          $this->head = $this->head->next;
        $lastNode = null;
      } else {
        $previousToLast->next = $lastNode->next;
        $lastNode = null;
      }
    }
  }
} 

下面是一个完整的程序，它使用上面讨论的概念来删除最后一次出现的指定键（如果存在）循环单链表。

<?php
//节点结构
class Node {
  public $data;
  public $next;
}

class LinkedList {
  public $head;

  public function __construct(){
    $this->head = null;
  }
  
  //在列表末尾添加新元素
  public function push_back($newElement) {
    $newNode = new Node();
    $newNode->data = $newElement;
    $newNode->next = null; 
    if($this->head == null) {
      $this->head = $newNode;
      $newNode->next = $this->head;
    } else {
      $temp = new Node();
      $temp = $this->head;
      while($temp->next !== $this->head) {
        $temp = $temp->next;
      }
      $temp->next = $newNode;
      $newNode->next = $this->head;
    }    
  }

  //通过key删除最后一个节点
  public function pop_last($key) {       
    if($this->head != null) {
      $temp = new Node();
      $previousToLast = null;
      $lastNode = null;
      
      if($this->head->data == $key) 
        $lastNode = $this->head;
      
      $temp = $this->head;
      while($temp->next != $this->head) {
        if($temp->next->data == $key) {
          $previousToLast = $temp;
          $lastNode = $temp->next;
        }
        $temp = $temp->next;
      }
   
      if($lastNode != null) {
        if($lastNode == $this->head) {
          if($this->head->next == $this->head)
            $this->head = null;
          else
            $this->head = $this->head->next;
          $lastNode = null;
        } else {
          $previousToLast->next = $lastNode->next;
          $lastNode = null;
        }
      }
    }
  } 

  //显示列表内容
  public function PrintList() {
    $temp = new Node();
    $temp = $this->head;
    if($temp != null) {
      echo "The list contains: ";
      while(true) {
        echo $temp->data." ";
        $temp = $temp->next;
        if($temp == $this->head)
          break;        
      }
      echo "\n";
    } else {
      echo "The list is empty.\n";
    }
  }    
};

//测试代码
$MyList = new LinkedList();

//列表中添加五个元素。
$MyList->push_back(10);
$MyList->push_back(20);
$MyList->push_back(30);
$MyList->push_back(20);
$MyList->push_back(40);
$MyList->PrintList();

//删除最后出现的20
$MyList->pop_last(20);
$MyList->PrintList(); 
?>

上面的代码将给出以下输出:

The list contains: 10 20 30 20 40 
The list contains: 10 20 30 40