PHP 删除循环单链表的奇数节点

 PHP 数据结构

删除循环单链表的奇数节点需要遍历链表，将奇数节点一一删除。它涉及以下过程。如果列表仅包含头，则将头设为空。如果列表包含多个元素，则删除头部并调整最后一个元素与新头部的链接。如果 head 的 next 不是 head，则创建三个节点 - evenNode 指向 head，oddNode 指向 head 的下一个，temp 存储最后一个偶节点。然后删除oddNode并将evenNode和oddNode更新为下一组奇偶节点，并继续该过程直到任何节点到达头部。之后，如果 evenNode 到达 head，则将 temp 的下一个作为头，否则将 evenNode 的下一个作为头。

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

public function deleteOddNodes() {
  //1.如果 head 是唯一的元素
  //列表使头部为空
  if($this->head != null && $this->head->next == $this->head) {
    $this->head = null;
  } else if($this->head != null) {

    //2。如果列表包含多个元素
    //删除头部并调整链接
    //带有新头的最后一个元素
    $temp = $this->head;
    while($temp->next != $this->head) {
      $temp = $temp->next;
    }
    $temp->next = $this->head->next;
    $this->head = null;
    $this->head = $temp->next;

    //3。创建 EvenNode 节点 - 指向 head
    // oddNode 节点 - 指向头的下一个
    // 临时节点 - 存储最后一个偶数节点
    if($this->head != null && $this->head->next != $this->head) {

      $evenNode = $this->head;
      $oddNode = $this->head->next; 
      while(true) {
        
        //4。删除奇数节点并更新偶数节点和
        // oddNode 到下一组奇偶节点更新
        //临时节点到最新的evenNode节点继续
        //直到任何节点到达头部为止的过程
        $temp = $evenNode;
        $evenNode->next = $oddNode->next;
        $oddNode = null;
        $evenNode = $evenNode->next;
        $oddNode = $evenNode->next;
        if($evenNode == $this->head || $oddNode == $this->head)
          break;
      }
      
      //5。如果 EvenNode 到达 head，则生成 temp 的下一个
      // 作为头，否则将 EvenNode 的下一个作为头
      if($evenNode == $this->head)
        $temp->next = $this->head;
      else
        $evenNode->next = $this->head;
    }
  } 
} 

下面是一个完整的程序，它使用了上面讨论的删除循环单链表奇数节点的概念。

<?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;
    }    
  }

  //删除链表的奇数节点
  public function deleteOddNodes() { 
    if($this->head != null && $this->head->next == $this->head) {
      $this->head = null;
    } else if($this->head != null) {
    
      $temp = $this->head;
      while($temp->next != $this->head) {
        $temp = $temp->next;
      }
      $temp->next = $this->head->next;
      $this->head = null;
      $this->head = $temp->next;

      if($this->head != null && $this->head->next != $this->head) {

        $evenNode = $this->head;
        $oddNode = $this->head->next; 
        while(true) {
          $temp = $evenNode;
          $evenNode->next = $oddNode->next;
          $oddNode = null;
          $evenNode = $evenNode->next;
          $oddNode = $evenNode->next;
          if($evenNode == $this->head || $oddNode == $this->head)
            break;
        }

        if($evenNode == $this->head)
          $temp->next = $this->head;
        else
          $evenNode->next = $this->head;
      }
    } 
  } 

  //显示列表内容
  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(40);
$MyList->push_back(50);

//显示列表内容。
$MyList->PrintList();

//删除链表的奇数节点
$MyList->deleteOddNodes();

echo "After deleting odd nodes:\n";
//显示列表内容。
$MyList->PrintList();
?>

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

The list contains: 10 20 30 40 50 
After deleting odd nodes:
The list contains: 20 40