크기가 알려지지 않은 순환 링크 된 목록의 마지막 노드를 찾고 마지막 노드는 링크 된 목록의 첫 번째 노드를 제외한 다른 노드를 가리 킵니다

Question

크기를 모르는 순환 링크 된 목록의 마지막 노드를 어떻게 찾을 수 있습니까? 마지막 노드는 연결된 목록의 첫 번째 노드를 제외한 다른 노드를 가리 킵니까?

Answer 1

노드가 순환 링크 된 목록의 첫 번째 노드를 가리 키지 않는 경우 정의하면
노드가 마지막 노드가 아닙니다.

여기에 설명해 주시겠습니까?

Answer 2

끝 부분에 있는지 알려주는 매개 변수를 목록의 노드에 추가 할 수 있습니까? 나는 그것이 문제가되지 않을 것이라고 생각한다.

그렇지 않으면 이미 visted 노드를 기억할 수 있습니다. 다음 노드가 이미 방문되면 끝이 난다.

Answer 3

이상한 목록 ... 왜 이런 식으로해야할까요? 하지만 어쨌든 ...

단순히 모든 노드를 반복 할 수 있으며 다음 노드가 이미 방문한 경우 바로 중지 할 수 있습니다. 그러면 현재 노드가 사용자의 대답이됩니다.

방문한 노드를 추적하는 방법이 필요합니다. 각 노드에 부울 플래그를 추가하거나 빠른 삽입 및 조회 (예 : 해시 세트)를 사용하는 일종의 설정된 데이터 유형을 사용하십시오. 이 사용할 수 있습니다

Answer 4

한 알고리즘은 플로이드주기 알고리즘은리스트의 마지막 요소를 제공하지 않습니다 this question.

Answer 5

를 참조 또한 Floyd cycle algorithm.

입니다. 주기가 있는지 여부 만 알 수 있습니다.

마지막 정의의 정의는 목록에서 첫 번째부터 순차적으로 검색하는 동안 그 앞에있는 모든 요소와 마지막 요소가 표시되지 않습니다 (포인터 값). 마지막으로이 순차 스캔에서 이미 본 첫 번째 요소가됩니다.

쉬운 해결책은 방문한 요소에 플래그를 지정하여 이미 본 요소를 쉽게 감지 할 수 있도록하는 것입니다. 플래그는 침입적일 수 있으며, 즉, 요소의 비트를 변경함으로써 또는 외부의 포인터 값을 저장하기 위해 해시 테이블을 사용함으로써 외부적일 수있다.

요소가 이미 방문되었는지 테스트 할 수 있어야하므로 다른 해결책이 표시되지 않습니다.

Answer 6

나는이 문제를 해결하기 위해 플로이드의 알고리즘을 사용하는 방법에 대해 자세히 설명 할 수 있지만 내가

1. 2 포인터가 연결리스트를 순회 가지고 한 단계에 대한 설명을 이해하지 못한다는 포인터 1은 1의 비율로가는 두 번째 노드는 2 노드의 속도로 이동합니다.
2. 포인터가 만났을 때 포인터 1이 사이클 끝까지 도달하기 전에 사이클이 진행되고 포인터 1이 도달하지 않았습니다 사이클이 거리 d이고 포인터 2가 1의 속도의 두 배가되면 pointer1은 포인터 1이 한 번 수행하기 전에주기를 두 번 반복하므로 종료합니다.
3. 그래서 포인터 1이주기를 완전히 지나치기 전에 만났기 때문에 회의 지점은 시작과 노드 사이의 d 노드 (pos = d + k)입니다.
4. 포인터 1을 position 0으로 설정하고 두 지점을 다시 시작합니다 (반복 당 1 노드 비율이 같음). 우리는주기의 시작을 알고 있기 때문에
5. 는 끝을 찾는 것은 4 단계에 해당하지만 난 친구가 나에게 솔루션을 설명했다 이유를 완전히 이해하지

간단하다.