연결된 목록이 원형인지 확인하십시오.

Question

기본 질문을 다시해서 죄송합니다. 답변을 찾고 있습니다. 이 질문에 대해 목록을 반복하는 속도가 빠르고 느린 포인터가 있어야하는 이유는 무엇입니까? 이

ptr = head->next; 
while(ptr != NULL) 
{ 
    if(ptr == head) 
    { 
     return true; 
    } 
    ptr = ptr->next; 
} 
return false; 

다음과 같이 논리를 갖는 하나의 포인터 안되는 이유 왜이 논리가 될 수없는 이유는 무엇입니까? 모든 대답은 두 가지 포인터 로직을 기반으로합니다.

Answer 1

두 개의 포인터가있을 필요는 없습니다. 예를 들어 이미 본 목록이나 포인터 테이블을 유지 한 다음 목록을 탐색하고 테이블을 참조하여 이미 포인터를 본 적이 있는지 여부를 확인하는 단일 포인터를 가질 수 있습니다.

두 포인터 솔루션이 테이블 조회 솔루션보다 유리한 점은 목록의 크기와 상관없이 두 포인터에 대한 추가 메모리 만 할당하면된다는 것입니다.

머리를 뒤집어 쓰는 목록에만 관심이있는 경우가 아니면 포인터 하나만 사용하여 머리를 검사 할 수 없습니다. 목록은 중간 어딘가에서 되돌아 갈 수 있습니다.

Answer 2

목록에 머리가 포함되어 있지 않은 루프가 있고 포인터 하나만있는 경우 어떻게 식별합니까? 당신은 꼼짝 못하게 되풀이 될 것입니다.
이 문제를 해결하려면 두 개의 포인터 (또는 이전 노드 목록 또는 이와 비슷한 목록)가 필요합니다.

Answer 3

여기 루프를 찾는 몇 가지 방법이 있습니다.

Answer 4

bool circular(node head*){ 
    //Honestly not sure if this should be true or false... 
    if(head->next == NULL) return false; 

    node ptr = head->next; 

    while(ptr != NULL) 
    { 
     if(ptr == head) 
     { 
      return true; 
     } 
     ptr = ptr->next; 
    } 
    return false; 
} 

http://ostermiller.org/find_loop_singly_linked_list.html

당신은이 포인터 ... 머리와 PTR 필요합니까.

머리가 어디에 있는지 추적해야하며 목록을 반복하는 데 포인터가 필요합니다.

귀하의 링크를 통해 읽기 : ptr == head.

편집이 때문에

또한, 구현으로 항상 true를 돌려줍니다 것이다.

는 또한 다른 노드 (단지 머리)

이 꽤 잘 고장이 링크를 통해 읽어 원형 있는지 확인해야합니다.

http://umairsaeed.com/2011/06/23/finding-the-start-of-a-loop-in-a-circular-linked-list/