php鏈表操作

1.

<?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 (); //獲取鏈表長度