연결리스트에서 링의 진입 노드를 찾는 PHP 구현 관련 지식 설명

이 글에서는 주로 순환 연결 목록에 대한 PHP의 순회, 검색, 계산 및 기타 관련 조작 기술을 포함하여 연결 목록에서 링의 진입 노드를 찾는 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;
}

#🎜 🎜## 🎜🎜#

당신이 관심을 가질 만한 기사:

PHP는 워터마크를 추가하고 생성할 수 있는 이미지 처리 도구 클래스를 구현합니다. Thumbnails_php Tips

PHP에서 지그재그 순서로 이진 트리를 인쇄하는 방법에 대한 설명

#🎜 🎜#PHP는 이진 트리 이미지를 얻는 방법을 설명합니다

위 내용은 연결리스트에서 링의 진입 노드를 찾는 PHP 구현 관련 지식 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!