연결된 목록에서 링의 항목 노드 인스턴스를 찾기 위한 PHP 구현에 대한 자세한 설명-PHP 튜토리얼-php.cn

연결된 목록에서 링의 항목 노드 인스턴스를 찾기 위한 PHP 구현에 대한 자세한 설명

小云云

풀어 주다： 2023-03-19 14:46:02

원래의

1522명이 탐색했습니다.

이 글에서는 주로 순환 연결 목록에 대한 PHP의 순회, 검색, 계산 및 기타 관련 작업 기술을 포함하여 연결 목록에서 링의 진입 노드를 찾는 PHP 구현을 소개합니다. 그것은 모두에게 도움이 될 수 있습니다.

Question

링크드 리스트에 링이 포함되어 있습니다. 링크드 리스트에서 링의 진입 노드를 찾아주세요.

솔루션 아이디어

첫 번째 단계는 링에서 교차점을 찾는 것입니다. p1과 p2를 사용하여 각각 연결된 목록의 선두를 가리킵니다. p1==p2가 링에서 교차점을 찾을 때까지 p1은 매번 한 단계를 수행하고 p2는 매번 두 단계를 수행합니다.
두 번째 단계는 반지의 입구를 찾는 것입니다. 이전 단계에 이어서, p1==p2일 때, p2가 통과한 노드의 수는 2x이고, p1이 통과한 노드의 수는 x라고 가정합니다. 링에는 n개의 노드가 있고, p2는 p1보다 한 바퀴 더 걷는다고 가정합니다. , 따라서 2x=n+x; n =x; p1이 실제로 링의 단계 수를 취하고 p2가 연결 목록의 선두를 가리키도록 하는 것을 볼 수 있습니다. p2는 p1==p2가 될 때까지 한 번에 한 걸음씩 나아갑니다. 이때 p1은 링의 입구를 가리킵니다. (아직도 이해가 안됨)

구현 코드

<?php
/*class ListNode{
  var $val;
  var $next = NULL;
  function __construct($x){
    $this->val = $x;
  }
}*/
function EntryNodeOfLoop($pHead)
{
  if($pHead == null || $pHead->next == null)
    return null;
  $p1 = $pHead;
  $p2 = $pHead;
  while($p2!=null && $p2->next!=null){
    $p1 = $p1->next;
    $p2 = $p2->next->next;
    if($p1 == $p2){
      $p2 = $pHead;
      while($p1!=$p2){
        $p1 = $p1->next;
        $p2 = $p2->next;
      }
      if($p1 == $p2)
        return $p1;
    }
  }
  return null;
}

로그인 후 복사