이번에는 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 중국어 웹사이트!
추천 자료:
위에서 아래로 이진 트리를 인쇄하기 위한 PHP 코드 공유
Z 모양 순서를 사용하여 PHP가 이진 트리를 인쇄하는 단계에 대한 자세한 설명
위 내용은 PHP를 사용하여 연결리스트에서 항목 노드를 찾는 단계에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!