PHP에서 링 연결 리스트를 사용하여 링의 진입 노드를 찾는 방법(코드 예)-PHP 튜토리얼-php.cn

PHP에서 링 연결 리스트를 사용하여 링의 진입 노드를 찾는 방법(코드 예)

不言

풀어 주다： 2023-04-04 07:16:02

원래의

1523명이 탐색했습니다.

이 글의 내용은 PHP에서 링 연결 리스트를 사용하여 링의 진입 노드(코드 예제)를 찾는 방법에 대한 것입니다. 필요한 친구들이 참고하면 도움이 될 것입니다. 당신.

연결된 리스트가 있고 링이 포함되어 있으면 연결리스트에서 링의 진입 노드를 찾고, 그렇지 않으면 null을 출력합니다.

1 연결리스트의 마지막에서 k번째 노드를 찾아 연결리스트를 입력합니다. , 연결된 리스트 k 노드에서 두 번째 노드를 출력합니다. 첫 번째 포인터는 k 번째 노드에 도달하기 위해 (k-1) 단계를 수행합니다. 두 포인터는 동시에 뒤로 이동합니다. 첫 번째 노드가 끝에 도달하면 두 번째 노드는 아래쪽에서 k 번째 노드에 위치합니다.

2. 원리는 위와 비슷합니다. 두 개의 포인터를 정의합니다. 하나는 매번 두 단계를 수행하는 빠른 포인터이고 다른 하나는 두 개가 만날 때 가정합니다. 링의 길이는 n 노트입니다. 느린 포인터는 x 단계를 수행하고 빠른 포인터는 2x 단계를 수행합니다. 2x=x+kn; 노드, 느린 포인터는 원래 위치에서 이동하지 않으며 둘은 하나를 수행합니다. 두 사람이 다시 만날 때 그들은 링의 입구에 있습니다. 링을 곧게 펴는 것을 상상해 보세요. 밑에서 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);

로그인 후 복사

object(Node)#1 (2) {
  ["data"]=>  string(0) ""
  ["next"]=>  object(Node)#2 (2) {
    ["data"]=>    string(3) "111"
    ["next"]=>    object(Node)#3 (2) {
      ["data"]=>      string(3) "222"
      ["next"]=>      object(Node)#4 (2) {
        ["data"]=>        string(3) "333"
        ["next"]=>        object(Node)#5 (2) {
          ["data"]=>          string(3) "444"
          ["next"]=>
          *RECURSION*
        }
      }
    }
  }
}object(Node)#3 (2) {
  ["data"]=>  string(3) "222"
  ["next"]=>  object(Node)#4 (2) {
    ["data"]=>    string(3) "333"
    ["next"]=>    object(Node)#5 (2) {
      ["data"]=>      string(3) "444"
      ["next"]=>
      *RECURSION*
    }
  }
}

로그인 후 복사