단일 연결 리스트가 회문인지 확인하는 JavaScript 프로그램

단방향 연결 리스트는 메모리에 불연속적으로 저장되는 선형 데이터 구조로, 각 블록은 다음 블록(노드라고도 함)의 주소를 보유하여 연결됩니다. 회문은 문자, 숫자 등의 집합으로 해석될 수 있으며 앞뒤에서 동일하게 읽혀집니다. 우리는 단일 연결 리스트를 얻고 노드에 저장된 값이 앞뒤에서 동일한지 확인해야 합니다.

들어가세요

으아아아

출력

으아아아

지침

첫 번째 노드와 마지막 노드의 값이 같고, 마지막 노드에서 두 번째와 두 번째 노드의 값이 같은 식으로 앞뒤에서 같은 거리에 있는 모든 노드는 같은 값을 갖는 것을 알 수 있습니다.

들어가세요

으아아아

출력

으아아아

지침

여기서 첫 번째와 두 번째 노드는 각각 마지막 및 두 번째 노드와 동일하지만 그 이후의 노드는 동일한 값을 갖지 않습니다.

스택을 사용하세요

이 방법에서는 먼저 이 클래스를 사용하여 연결 목록을 만든 다음 연결 목록에 데이터를 추가하고 연결 목록에 있는 데이터를 인쇄하는 몇 가지 기본 함수를 정의합니다.

예

으아아아

시간과 공간의 복잡성

위 코드의 시간 복잡도는 O(N)입니다. 여기서 N은 연결 리스트의 길이입니다.

위 코드의 공간 복잡도는 스택 데이터 구조를 사용하여 요소를 저장하기 때문에 O(N)입니다.

재귀 사용

이 방법에서는 먼저 주어진 연결 목록의 길이를 찾은 다음 재귀를 사용하여 연결 목록의 중간까지 이동합니다. 주어진 연결 리스트의 길이가 홀수이면 다음 노드를 중간 노드로 반환하고, 그렇지 않으면 중간 노드를 반환하며, 각 호출에 대해 재귀 호출에서 뒤에서 해당 노드를 가져옵니다.

예

으아아아

결론

이 튜토리얼에서는 주어진 연결된 목록 노드에 회문의 값이 포함되어 있는지 확인하는 JavaScript 프로그램을 구현했습니다. 스택과 재귀를 사용하여 두 가지 코드를 구현했습니다. 스택의 시간 복잡도는 O(N)이고 재귀 방법의 공간 복잡도는 O(1)입니다. 고려하지 않음).

위 내용은 단일 연결 리스트가 회문인지 확인하는 JavaScript 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!