PHP 在循环单链表中的给定位置插入新节点

 PHP 数据结构

在此方法中，将一个新元素插入到循环单链表中的指定位置。例如 - 如果给定列表为 10->20->30，并且在位置 2 添加新元素 100，则列表将变为 10->100->20->30。

首先，创建两个节点: 1. newNode 具有给定元素和 2. temp 遍历列表。然后统计列表中元素的个数，检查插入位置是否有效（必须在[1, n + 1]范围内，其中n 是列表中的元素数量）。如果插入位置有效且等于 1，则将 newNode 作为头并相应地调整链接。如果插入位置有效且大于1则遍历到指定位置插入newNode并相应调整链接。

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

public function push_at($newElement, $position) {     

  //1.将节点分配给新元素并
  // 创建一个临时节点来遍历列表
  $newNode = new Node(); 
  $newNode->data = $newElement;
  $newNode->next = null;
  $temp = $this->head;
  $NoOfElements = 0;

  //2。查找列表中元素的数量
  if($temp != null) {
    $NoOfElements++;
    $temp = $temp->next;
  }
  while($temp != $this->head) {
    $NoOfElements++;
    $temp = $temp->next;
  }

  //3。检查插入位置是否有效
  if($position < 1 || $position > ($NoOfElements+1)) {
    echo "\nInvalid position.";
  } else if ($position == 1) {
  
  //4。如果位置为 1，则进行下一个
  //新节点作为头，新节点作为头
    if($this->head == null) {
      $this->head = $newNode;
      $this->head->next = $this->head;
    } else {
      while($temp->next != $this->head) {
        $temp = $temp->next;
      }
      $newNode->next = $this->head;
      $this->head = $newNode;
      $temp->next = $this->head;
    }
  } else {

   //5。否则，遍历到之前的节点
   //给定位置，将newNode作为下一个
   // 作为 temp next 和 temp next 作为 newNode。
    $temp = $this->head;
    for($i = 1; $i < $position-1; $i++) 
      $temp = $temp->next;
    $newNode->next = $temp->next;
    $temp->next = $newNode;  
  }
} 

下面是一个完整的程序，它使用上面讨论的概念在循环中的给定位置单独插入一个新节点链表。

<?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 push_at($newElement, $position) {     

   $newNode = new Node(); 
    $newNode->data = $newElement;
    $newNode->next = null;
    $temp = $this->head;
    $NoOfElements = 0;

    if($temp != null) {
      $NoOfElements++;
      $temp = $temp->next;
    }
    while($temp != $this->head) {
      $NoOfElements++;
      $temp = $temp->next;
    }

    if($position < 1 || $position > ($NoOfElements+1)) {
      echo "\nInvalid position.";
    } else if ($position == 1) {
  
      if($this->head == null) {
        $this->head = $newNode;
        $this->head->next = $this->head;
      } else {
        while($temp->next != $this->head) {
          $temp = $temp->next;
        }
        $newNode->next = $this->head;
        $this->head = $newNode;
        $temp->next = $this->head;
      }
    } else {
      $temp = $this->head;
      for($i = 1; $i < $position-1; $i++) 
        $temp = $temp->next;
      $newNode->next = $temp->next;
      $temp->next = $newNode;  
    }
  } 

  //显示列表内容
  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->PrintList();

//在位置2插入一个元素
$MyList->push_at(100, 2);
$MyList->PrintList();

//在位置1插入一个元素
$MyList->push_at(200, 1);
$MyList->PrintList(); 
?>

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

The list contains: 10 20 30 
The list contains: 10 100 20 30 
The list contains: 200 10 100 20 30