如何从链表的根节点中区分“仅有另一个节点”具有相同的值，同时检查列表是否是循环的？

Question

以下是最简单的形式我的类定义 -

class Node 
{ 
    public $data; 
    public $next = null; 

    public function __construct($data) 
    { 
     $this->data = $data; 
    } 
} 

class LinkedList 
{ 
    public $root; 

//should have named checkIfCircular 
    public function checkIfCyclic() 
    { 
     $rootVal = $this->root->data; 
     $isCyclic = false; 

     //start iterating from the root, through the length of the ll and see if the root is encountered again. 
     $node = $this->root; 
     while($node->next!=null) 
     { 
      echo "<br>traversing ".$node->next->data." comparison ".($node->next === $this->root)." and ".($node->next == $this->root); 
      //case 2 -> strict comparison does not differentiate as expected here. Evaluates to true even in case of $ll2. 
      if($node->next === $this->root) 
      { 
       $isCyclic = true; 
       break; 
      } 
      else 
      { 
       $node=$node->next; 
      } 
     } 
     return $isCyclic; 
    } 
} 

以下是我如何初始化两个链接列表 -

//3->4->5->6->first node 
$ll = new LinkedList(); 
$ll->root = new Node(3); 
$ll->root->next = new Node(4); 
$ll->root->next->next = new Node(5); 
$ll->root->next->next->next = new Node(6); 
$ll->root->next->next->next->next = $ll->root; 
echo "<br>see ll ".$ll->checkIfCyclic(); 


//3->4->5->6->3 (a different 3) 
$ll2 = new LinkedList(); 
$ll2->root = new Node(3); 
$ll2->root->next = new Node(4); 
$ll2->root->next->next = new Node(5); 
$ll2->root->next->next->next = new Node(6); 
$ll2->root->next->next->next->next = new Node(3); 
echo "<br>see ll2 ".$ll->checkIfCyclic(); 

以下是我的输出 -

traversing 4 comparison and 
traversing 5 comparison and 
traversing 6 comparison and 
traversing 3 comparison 1 and 1 
see ll 1 
traversing 4 comparison and 
traversing 5 comparison and 
traversing 6 comparison and 
traversing 3 comparison 1 and 1 //I expected the 1st comparison to return false here 
see ll2 1 

我本来希望ll2能够返回false。

然而，这个工程按照我的意料 -

$something = new Node(3); 
$another = $something; 
echo "compare same ".($something===$another)." and ".($something==$another)."<br>"; 

$something = new Node(3); 
$another = new Node(3); 
echo "compare different ".($something===$another)." and ".($something==$another)."<br>"; 

我缺少什么？

Answer 1

这是你的问题。你跟$ll而不是$ll2把它称为：

echo "<br>see ll2 ".$ll->checkIfCyclic();