PHP-Implementierungsbeispiel für den Flip-Vorgang einer einfach verknüpften Liste

Wenn eine Sequenz nur Links enthält, die auf ihre Nachfolgeknoten verweisen, wird die verknüpfte Liste als einfach verknüpfte Liste bezeichnet. In diesem Artikel wird hauptsächlich die Implementierung der einfach verknüpften Listenoperation in PHP vorgestellt und die Definition, Durchquerung, Rekursion, Umkehrung und andere verwandte Operationen der einfach verknüpften Liste in PHP anhand von Beispielen analysiert. Ich hoffe, es kann allen helfen.

Hier ist die Definition einer einfach verknüpften Liste und der Flip-Operationsmethode:

<?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();
?>

Laufergebnisse:

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

Verwandte Empfehlungen:
Python-Implementierung von Singlely Linked Liste

PHP Single Linked List Flip

PHP-Code PHP Single Linked List Implementierungscode

Das obige ist der detaillierte Inhalt vonPHP-Implementierungsbeispiel für den Flip-Vorgang einer einfach verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!