두 개의 포인터가없는 연결된 목록의 루프가

Question

인 경우 연결된 목록에 루프가 있는지 찾아보십시오. 빠른 포인터와 느린 포인터를 사용하는 대신 다른 방법이 있습니까? ?

Answer 1

상황에 따라이를 수행 할 수있는 다양한 방법이 있습니다.

1. 도달 할 때 어떤 종류의 세트에 각 노드를 추가하십시오. 끝까지 도달하거나 세트에 이미있는 노드를 찾을 때까지 목록을 살펴보십시오.

2. 노드에 여유 공간이있는 경우 각 노드를 "방문한"것으로 표시하거나 표시하지 않고 이미 마크 한 노드를 찾을 때까지 목록을 이동할 수 있습니다. 두 포인터 방법은 추가 메모리를 사용하여 거의 모든 곳에서 적용하지 않는 동안

이

은 물론, 모두가 그들이 사용할 수없는 것 (높은 메모리 사용 등) 단점이나 상황이있다.

Answer 2

각 노드를 방문한 것으로 표시하고 이미 방문한 노드가 있음을 감지해야합니다. 문제는 그것을 표시 할 것이므로 목록을 실행하여 전후의 모든 것을 재설정 할 필요가 없습니다.

Answer 3

이전 솔루션에서 말한 것처럼, 방문한 노드를 어떻게 든 표시해야합니다. 실제로 모든 단일 링크 목록 노드에서 모든 메모리 주소가 8의 배수이기 때문에 "next"포인터에 적어도 3 비트의 여유 공간이 있습니다. 따라서 해킹을 조금 할 수 있으며 마지막으로 예를 들어 설정할 수 있습니다 링크 된리스트에서 전진 할 때 '다음'포인터의 마지막 비트를 가려서 유효한 메모리 주소를 가져야합니다.