연결된 목록에서 루프의 길이를 찾는 JavaScript 프로그램

이 프로그램에서는 루프를 포함할 수 있는 연결 목록을 얻고 루프가 존재하는지 확인한 다음 루프의 크기를 알아내야 합니다. 코드의 도움으로 루프의 길이를 찾는 매우 유명한 방법을 사용하고 시간 및 공간 복잡성에 대해 논의해 보겠습니다.

문제 소개

이 질문에서는 위에서 본 것처럼 루프를 포함할 수도 있고 포함하지 않을 수도 있는 연결 목록이 제공됩니다. 루프가 존재하면 루프의 길이를 찾아야 하며, 그렇지 않으면 0을 반환해야 합니다. 아니 주기가 있습니다. Floyd 루프 방법을 사용하여 루프를 찾은 다음 크기를 확인합니다. 예를 들어, 연결 리스트가 주어진다면 -

으아악

8을 포함하는 노드에서 4를 포함하는 노드까지 순환이 있습니다. 이는 8이 4와 연결되어 길이 5의 순환을 형성한다는 의미입니다. 이를 감지해야 합니다.

방법

이 질문에서는 플로이드 루프 방법을 사용하여 루프를 감지한 다음 길이 조회 개념을 사용하여 루프의 길이를 찾습니다. 먼저 문제의 기본 단계를 살펴본 후 프로이트식 방법과 길이식 방법으로 넘어가겠습니다.

• 먼저 연결리스트 노드의 기본 구조를 제공하는 클래스를 만들고 그 안에 생성자를 정의하여 노드 값을 초기화하겠습니다.

• 그런 다음 요소를 주어진 연결 목록에 푸시하는 함수를 만듭니다.

• 위 방법을 사용하여 연결 리스트를 만든 다음 마지막 노드를 다른 노드에 연결하여 그 안에 루프를 형성합니다.

프로이트의 알고리즘

이 알고리즘에서는 연결된 목록을 순회합니다. 연결된 목록에 들어가면 어떤 노드에서도 나갈 수 없습니다. 즉, 연결된 목록의 원형 부분에 두 개의 포인터가 있고 한 포인터는 한 번에 한 노드씩 이동하고 다른 포인터는 한 번에 두 노드를 이동하면 어느 시점에서 만나게 됩니다.

• 알고리즘을 구현한 후 함수를 호출하여 루프가 존재하는지 확인합니다

• 루프가 있으면 anther 함수를 호출하여 루프 길이를 알아냅니다.

• 한편, 돌아가서 루프가 존재하지 않는다고 인쇄하겠습니다.

예

아래 예에서는 연결된 목록을 정의하고 여기에 8개의 노드를 추가합니다. 노드 8을 노드 4에 연결하여 연결 리스트에 루프를 형성합니다. 따라서 5개의 노드로 구성된 루프를 형성합니다.

으아악

시간과 공간의 복잡성

위 코드에서는 전체 연결 목록을 한 번만 순회하고 루프 부분은 최대 3회 순회하므로 시간 복잡도가 선형이 됩니다. 따라서 위 코드의 시간 복잡도는 선형입니다. 즉, O(N)입니다. 여기서 N은 연결 목록의 크기입니다.

추가 공간을 사용하지 않으므로 프로그램의 시간 복잡도는 O(1)입니다.

결론

이 튜토리얼에서는 개념을 JavaScript 언어로 구현하여 연결 목록에 있는 루프의 길이를 찾는 방법을 배웠습니다. 우리는 Floyd의 루프 찾기 알고리즘을 사용하여 주어진 연결 목록에서 루프를 찾은 다음 while 루프를 사용하여 루프를 반복하고 길이를 찾았습니다. 위 코드의 시간복잡도는 O(N), 공간복잡도는 O(1)이다.

위 내용은 연결된 목록에서 루프의 길이를 찾는 JavaScript 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!