PHP实现单链表翻转操作示例

yipeiwu_com6年前PHP代码库

本文实例讲述了PHP实现单链表翻转操作。分享给大家供大家参考,具体如下:

当一个序列中只含有指向它的后继结点的链接时,就称该链表为单链表。

这里给出了一个单链表的定义及翻转操作方法:

<?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().' ';
    $tmpHead = $tmpHead->getNext();
  }
  echo "\n";
  //$head = reverse($head);
  $head = reverse2($head);
  while($head != null){
    echo $head->getValue().' ';
    $head = $head->getNext();
  }
}
test();
?>

运行结果:

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

更多关于PHP相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结

希望本文所述对大家PHP程序设计有所帮助。

相关文章

10条PHP编程习惯助你找工作

过去的几周对我来说是一段相当复杂的经历。我们公司进行了大裁员,我是其中之一,但却体验到了其中的乐趣。我从来没有被开除过,所以很难不去想得太多。我开始浏览招聘板块,一个全职PHP程序员的职...

PHP通过get方法获得form表单数据方法总结

PHP通过get方法获得form表单数据方法总结

我们在进行网页交互设计的时候,通常都会使用PHP中get变量方法来获得form表单中的数据,以此来实现各种网页动态查询或者请求。对于稍有HTML基础的朋友来说,应该都知道HTML for...

深入PHP内存相关的功能特性详解

可能有的读者碰到过类似下面的错误吧:Fatal error: Allowed memory size of X bytes exhausted (tried to allocate Y...

php中判断一个字符串包含另一个字符串的方法

第一种方法:用php的strpos() 函数判断字符串中是否包含某字符串的方法 if(strpos('www.jb51.net','jb51') !== false){ echo...

php中mail函数发送邮件失败的解决方法

本文实例讲述了php中mail函数发送邮件失败的解决方法。分享给大家供大家参考。具体分析如下: php中mail函数是一个自带的发邮件的函数,但是如果你真的要使用mail函数来发邮件那必...