Exemple d'implémentation PHP d'une opération de retournement de liste à chaînage unique

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. Cet article présente principalement l'implémentation de l'opération de retournement de liste à chaînage 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înage unique PHP sous forme d'exemples. Les amis qui en ont besoin peuvent s'y référer. J'espère que cela pourra aider tout le monde.

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

Recommandations associées :
Implémentation Python de liens simples list

Flip de liste à chaînage unique PHP

code php Code d'implémentation de liste à chaînage unique PHP

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!