php链表操作

<?php
//单链表 
class node {   

    public $id; //节点id   
    public $name; //节点名称   
    public $next; //下一节点   
    public function __construct($id, $name) {   
        $this->id = $id;   
        $this->name = $name;   
        $this->next = null;   
    }   
}  


class singelNodeList {   
    private $header; //链表头节点    
    public function __construct($id = null, $name = null) {   //构造方法   
        $this->header = new node ( $id, $name, null );   
    }   

   

    //获取链表长度   
    public function getNodeLength() {   
        $i = 0;   
        $current = $this->header;   
        while ( $current->next != null ) {   
            $i ++;   
            $current = $current->next;   
        }   
        return $i;   
    }   

   

    //添加节点数据   
    public function addLink($node) {   
        $current = $this->header;   
        while ( $current->next != null ) {   
            if ($current->next->id > $node->id) {   
                break;   
            }   
            $current = $current->next;   
        }   
        $node->next = $current->next;   
        $current->next = $node;   
    }   

   

    //删除链表节点   
    public function delLink($id) {   
        $current = $this->header;   
        $flag = false;   
        while ( $current->next != null ) {   
            if ($current->next->id == $id) {   
                $flag = true;   
                break;   
            }   
            $current = $current->next;   
        }   
        if ($flag) {   
            $current->next = $current->next->next;   
        } else {   
            echo "未找到id=" . $id . "的节点！<br>";   
        }   
    }  

   

    //判断连表是否为空  
    public function isEmpty(){  
          return $this->header == null;  

    }  

  
    //清空链表  
    public function clear(){  
        $this->header = null;  

    }   

    //获取链表   
    public function getNodeList() {   
        $current = $this->header;   
        if ($current->next == null) {   
            echo ("链表为空!");   
            return;   
        }   
        while ( $current->next != null ) {   
            echo 'id:' . $current->next->id . '   name:' . $current->next->name . "<br>";   
            if ($current->next->next == null) {   
                break;   
            }   
            $current = $current->next;   
        }   
    }   

   

    //获取节点名字   
    public function getNodeNameById($id) {   
        $current = $this->header;   
        if ($current->next == null) {   
            echo "链表为空!";   
            return;   
        }   
        while ( $current->next != null ) {   
            if ($current->id == $id) {   
                break;   
            }   
            $current = $current->next;   
        }   
        return $current->name;   

    }   

   

    //更新节点名称   
    public function updateNode($id, $name) {   
        $current = $this->header;   
        if ($current->next == null) {   
            echo "链表为空!";   
            return;   
        }   
        while ( $current->next != null ) {   
            if ($current->id == $id) {   
                break;   
            }   
            $current = $current->next;   
        }   
        return $current->name = $name;   
    }  

// function eatList(Node $node){ 
function eatList($this->header){ 
    $fast = $slow = $node;
    $first_target = null;
    if($node->data == null) {
        return false;
    }

    while (true) {
        if($fast->next != null && $fast->next->next != null) {
            $fast = $fast->next->next;      // 快指针一次走两步
            $slow = $slow->next;            // 慢指针一次走一步
        } else {
            return false;
        }

        if($fast == $slow) {                // 慢指针追上快指针,说明有环
            $p1 = $node;                    // p1指针指向head节点,p2指针指向它们第一次相交的点,
                                         // 然后两个指针每次移动一步,当它们再次相交,即为 环的入口
            $p2 = $fast;
            while($p1 != $p2) {
                $p1 = $p1->next;
                $p2 = $p2->next;
            }
            return $p1;                     // 环的入口节点$
        } 
    }
}



}  

$lists = new singelNodeList ();   

$lists->addLink ( new node ( 5, 'eeeeee' ) );   
$lists->addLink ( new node ( 1, 'aaaaaa' ) );  
$lists->addLink ( new node ( 6, 'ffffff' ) );   
$lists->addLink ( new node ( 4, 'dddddd' ) );   
$lists->addLink ( new node ( 3, 'cccccc' ) );   
$lists->addLink ( new node ( 2, 'bbbbbb' ) );   
$lists->addLink ( new node ( 4, 'bbbbbb' ) );  
$lists->addLink ( new node ( 3, 'bbbbbb' ) );  
$lists->addLink ( new node ( 2, 'bbbbbb' ) );  



print_r($this->eatList($list));
// $lists->delLink ( 5 );    //删除节点5

$lists->getNodeList ();   


$lists->updateNode ( 3, "222222" );    //更新节点名称

// $lists->getNodeList ();  


echo $lists->getNodeNameById ( 5 );  //获取节点名称


echo $lists->getNodeLength (); //获取链表长度