PHP でリングリンクリストを使用してリングのエントリノードを見つける方法 (コード例)

この記事の内容は、PHP でリンクリスト内のリングのエントリノードを見つける方法 (コード例) についてです。一定の参考値があります。必要な友人は参考にしてください。お役に立てば幸いです。あなたに。役に立ちます。

リンク リストが指定された場合、リングが含まれている場合は、リンク リストでリングのエントリ ノードを見つけてください。それ以外の場合は、null を出力します。

1. リストから k 番目のノードを見つけます。リンク リストの一番下にあるリンク リストを 1 つ入力すると、リンク リストの最後から k 番目のノードが出力されます。最初のポインタは k 番目のノードに到達するまでに (k-1) ステップかかります。2 つのポインタは同時に後方に移動します。最初のノードが終点に到達すると、2 番目のノードは下から k 番目のノードに位置します。 .

2. 原理は上記と少し似ており、2 つのポインタを定義します。1 つは毎回 2 ステップかかる高速ポインタ、もう 1 つは毎回 1 ステップかかる低速ポインタです。 n ノードの場合、低速ポインタは x ステップ、高速ポインタは 2x ステップかかります 2x=x kn; #3. 高速ポインタはヘッド ノードに戻り、低速ポインタは戻ります元の位置では動かない 二人は一歩ずつ進む 二人が再び出会う時はリングの入り口にいる リングをまっすぐにすると下からk番目 ノードはよく似ている

slow fast
while fast!=null && fast->next!=null
    slow=slow->next
    fast=fast->next->next
    if slow==fast
        fast=head
        while slow!=fast
            slow=slow->next
            fast=fast->next
        if slow==fast
            return slow
return null

<?php
class Node{
        public $data;
        public $next;
        public function __construct($data=""){
                $this->data=$data;
        }   
}
//构造一个带环的链表
$linkList=new Node();
$linkList->next=null;
$temp=$linkList;

$node1=new Node("111");
$temp->next=$node1;
$temp=$node1;

$node2=new Node("222");
$temp->next=$node2;
$temp=$node2;

$node3=new Node("333");
$temp->next=$node3;
$temp=$node3;

$node4=new Node("444");
$temp->next=$node4;
$node4->next=$node2;//尾结点指向第二个结点

function EntryNodeOfLoop($pHead){
        $slow=$pHead;
        $fast=$pHead;
        while($fast!=null && $fast->next!=null){
                $slow=$slow->next;//慢指针走一步
                $fast=$fast->next->next;//快指针走两步
                //快慢指针环内相遇
                if($slow==$fast){
                        //快指针回到头结点
                        $fast=$pHead;
                        //同一速度再同时走
                        while($slow!=$fast){
                                $slow=$slow->next;
                                $fast=$fast->next;
                        }   
                        //两个相遇的点一定是环的入口
                        if($slow==$fast){
                                return $fast;
                        }   
                }   
        }   
}
var_dump($linkList);
$result=EntryNodeOfLoop($linkList);
var_dump($result);

rreee
関連する推奨事項:

リンク リスト内のリングのエントリ ノードを見つけるための PHP 実装

PHP 実装循環リンク リスト関数

以上がPHP でリングリンクリストを使用してリングのエントリノードを見つける方法 (コード例)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。