Implémentation PHP d'un exemple d'opération de retournement de liste chaînée unique

Cet article présente principalement l'implémentation de l'opération de retournement de liste chaînée unique en PHP et analyse la définition, le parcours, la récursivité, le retournement et d'autres compétences opérationnelles connexes de la liste chaînée simple PHP sous forme d'exemples auxquels les amis dans le besoin peuvent se référer.

Cet article L'exemple décrit l'implémentation d'une opération de retournement de liste à chaînage unique en PHP. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Lorsqu'une séquence ne contient que des liens pointant vers ses nœuds successeurs, la liste chaînée est appelée liste chaînée unique.

Voici la définition d'une liste à chaînage unique et la méthode d'opération de retournement :

<?php
/**
 * @file reverseLink.php
 * @author showersun
 * @date 2016/03/01 10:33:25
 **/
class Node{
  private $value;
  private $next;
  public function __construct($value=null){
    $this->value = $value;
  }
  public function getValue(){
    return $this->value;
  }
  public function setValue($value){
    $this->value = $value;
  }
  public function getNext(){
    return $this->next;
  }
  public function setNext($next){
    $this->next = $next;
  }
}
//遍历，将当前节点的下一个节点缓存后更改当前节点指针 
function reverse($head){
  if($head == null){
    return $head;
  }
  $pre = $head;//注意：对象的赋值
  $cur = $head->getNext();
  $next = null;
  while($cur != null){
    $next = $cur->getNext();
    $cur->setNext($pre);
    $pre = $cur;
    $cur = $next;
  }
  //将原链表的头节点的下一个节点置为null，再将反转后的头节点赋给head 
  $head->setNext(null);
  $head = $pre;
  return $head;
}
//递归，在反转当前节点之前先反转后续节点 
function reverse2($head){
  if (null == $head || null == $head->getNext()) {
    return $head;
  }
  $reversedHead = reverse2($head->getNext());
  $head->getNext()->setNext($head);
  $head->setNext(null);
  return $reversedHead;
}
function test(){
  $head = new Node(0);
  $tmp = null;
  $cur = null;
  // 构造一个长度为10的链表，保存头节点对象head  
  for($i=1;$i<10;$i++){
    $tmp = new Node($i);
    if($i == 1){
      $head->setNext($tmp);
    }else{
      $cur->setNext($tmp);
    }
    $cur = $tmp;
  }
  //print_r($head);exit;
  $tmpHead = $head;
  while($tmpHead != null){
    echo $tmpHead->getValue().&#39; &#39;;
    $tmpHead = $tmpHead->getNext();
  }
  echo "\n";
  //$head = reverse($head);
  $head = reverse2($head);
  while($head != null){
    echo $head->getValue().&#39; &#39;;
    $head = $head->getNext();
  }
}
test();
?>

Résultats d'exécution :

0 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 0

Articles qui pourraient vous intéresser :

Explication de comment fusionner deux tableaux ordonnés en PHP

Explication détaillée de la méthode d'implémentation du problème Joseph Ring en PHP

Explication de la méthode d'utilisation de Passport pour implémenter Authentification d'authentification dans Laravel5.5

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!