Example of single linked list flip operation implemented by PHP

  • 2021-08-21 19:54:10
  • OfStack

In this paper, an example is given to describe the implementation of single linked list flip operation by PHP. Share it for your reference, as follows:

When a sequence contains only links to its successor nodes, it is called a single linked list.

Here, the definition of a single linked list and the flip operation method are given:


<?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;
  }
}
// Traversal, will the current node under the 1 Change the current node pointer after 1 node cache  
function reverse($head){
  if($head == null){
    return $head;
  }
  $pre = $head;// Note: Assignment of objects 
  $cur = $head->getNext();
  $next = null;
  while($cur != null){
    $next = $cur->getNext();
    $cur->setNext($pre);
    $pre = $cur;
    $cur = $next;
  }
  // The header node of the original linked list is under 1 Nodes are set to null And assign the inverted header node to head 
  $head->setNext(null);
  $head = $pre;
  return $head;
}
// Recursion, which reverses subsequent nodes before reversing the current node  
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;
  //  Structure 1 The length is 10 The linked list of, saving the header node object 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().' ';
    $tmpHead = $tmpHead->getNext();
  }
  echo "\n";
  //$head = reverse($head);
  $head = reverse2($head);
  while($head != null){
    echo $head->getValue().' ';
    $head = $head->getNext();
  }
}
test();
?>

Run results:


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

For more readers interested in PHP related contents, please check the topics of this site: "PHP Data Structure and Algorithm Tutorial", "php Programming Algorithm Summary", "php String (string) Usage Summary", "PHP Array (Array) Operation Skills Complete Book", "PHP Common Traversal Algorithms and Skills Summary" and "PHP Mathematical Operation Skills Summary"

I hope this article is helpful to everyone's PHP programming.


Related articles: