연결리스트에서 순환을 감지하는 Python 프로그램

연결리스트의 어떤 노드도 NULL을 가리키지 않으면 연결리스트에 순환이 있다고 합니다. 마지막 노드는 연결리스트의 이전 노드를 가리키며 루프를 생성합니다. 링이 있는 연결리스트에는 끝점이 없습니다.

아래 예시에서 마지막 노드(노드 5)는 NULL을 가리키지 않습니다. 대신 노드 3을 가리키고 루프를 설정합니다. 따라서 위의 연결 목록은 끝이 없습니다.

두 개의 포인터를 얻는 알고리즘은 빠르고 느립니다

• 두 포인터 모두 처음에는 연결 목록의 HEAD를 가리킵니다.

• 느린 포인터는 항상 1씩 증가하고, 빠른 포인터는 항상 2씩 증가합니다.

• 언제든지 빠른 포인터와 느린 포인터가 동일한 노드를 가리키면 연결된 목록에 주기가 있다고 합니다.

마지막 노드가 두 번째 노드를 가리키는 다음 연결 목록 예제를 고려해보세요. -

예

느린 포인터와 빠른 포인터는 모두 동일한 노드를 가리킵니다. 따라서 주어진 연결리스트에는 순환이 포함되어 있다고 결론을 내릴 수 있습니다.

으아아아

출력

연결된 목록에서 주기가 감지되었습니다.

으으으으

위 내용은 연결리스트에서 순환을 감지하는 Python 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!