단일 반복으로 완료되는 연결 목록의 중간 요소를 가져오는 Python 프로그램

연결된 목록은 연속되지 않은 메모리 위치에 데이터를 저장하는 데 사용됩니다. 데이터 항목을 포함하는 노드는 포인터를 사용하여 연결됩니다. 각 노드는 두 개의 필드로 구성됩니다. 첫 번째 필드는 데이터를 저장하는 데 사용되고 두 번째 필드에는 다음 노드에 대한 링크가 포함됩니다.

무차별 대입 크래킹 기술

연결 목록의 중간 요소를 찾기 위해 무차별 대입 기법은 NULL이 나타날 때까지 전체 연결 목록을 반복한 다음 길이를 2로 나누어 연결 목록의 중간 요소를 얻는 방식으로 연결 목록의 길이를 찾는 것입니다. 목록의 색인. 중간 요소의 인덱스를 얻은 후 연결리스트를 처음부터 다시 반복하고 필요한 인덱스에 도달하면 중지합니다. 이 인덱스의 데이터 항목은 중간 요소를 제공합니다.

• HEAD를 가리키는 "temp"라는 변수를 가져와 "len"을 0

으로 초기화합니다.

• temp를 사용하여 NULL에 도달할 때까지 연결된 목록을 반복하고 각 노드에서 "len"을 1씩 증가시킵니다.

• 연결리스트의 길이를 구한 후 임시를 HEAD로 다시 초기화하세요. len//2까지 연결리스트를 반복합니다.

느리고 빠른 포인터 사용(단일 반복)

연결된 목록을 탐색하기 위해 두 개의 포인터를 사용합니다. 하나는 "느린 포인터"이고 다른 하나는 "빠른 포인터"입니다.

빠른 포인터는 느린 포인터보다 두 배 빠르게 움직입니다.

빠른 포인터가 연결 목록의 끝에 도달하면 느린 포인터가 중간 노드에 있게 됩니다.

따라서 중간 노드의 내용을 직접 인쇄할 수 있습니다.

예

아래 링크 목록을 고려해보세요. 중간 요소는 3입니다.

빠른 포인터는 연결 목록의 마지막 노드에 도달했고 느린 포인터는 이제 노드 3을 가리킵니다. 따라서 3은 주어진 연결리스트의 중간 요소입니다. 이제 6개의 노드를 고려해보세요.

예

빠른 포인터가 NULL에 도달했고 느린 포인터가 4번째 노드를 가리킵니다. 따라서 중간 요소는 4입니다.

알고리즘

• "느린" 및 "빠른" 지점이 연결 목록의 HEAD를 가리키도록 만듭니다.

• 빠른 포인터와 fast.next가 NULL

이 아닐 때까지 빠른 포인터를 2로, 느린 포인터를 1로 늘립니다.

• 느린 포인터에 값을 인쇄합니다.

• 시간 복잡도는 O(n)입니다.

으아악

출력

으으으으

위 내용은 단일 반복으로 완료되는 연결 목록의 중간 요소를 가져오는 Python 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!