가능한 중복 : 모든
Best algorithm to test if a linked list has a cycle이 코드가 연결된 목록에서 루프를 찾는 방법은 무엇입니까?
p=head;
q=head->next;
while(p!=NULL && q!=NULL)
{
if(p==q) { //Loop detected! exit(0); }
p=p->next;
q=(q->next)?(q->next->next):q->next; --how this line works ??
}
첫째, 목록에 루프가없는 경우 q 앞서 "항상 같은 조건이 p==q이 사실이 없을 것 p입니다.
그런 다음 p과 q 사이의 거리가 매 반복마다 1 씩 증가합니다. 따라서 루프가있는 경우 길이가 루프 길이의 정수 배가 되 자마자 p==q 조건이 true가됩니다.
해당 줄은 q을 2 칸 앞으로 이동합니다. 먼저 NULL 포인터 역 참조를 피하기 위해 q이 단 하나의 위치로 앞으로 이동 한 다음 목록 끝까지 도달하지 않는지 먼저 확인합니다. (q->next는 q->next->next 앞서 두 위치이며, 한 위치 앞서 q이다.)
인용구 :
Q = (Q-> 다음) (Q->하는 next-> 다음) : Q-> 다음 것; -이 선은 어떻게 작동합니까 ??
이도 읽을 수 있습니다 : 링크 된 목록에 루프가있는 경우
if(q->next) {
q = q->next->next;
} else {
q = q->next;
}
, 당신은 그것을 찾을 수 있으며, 하나의 목록을 하나 개의 요소에 의해 전진 목록을 두 개의 포인터를 실행하여 다른 두 요소로.
루프가없는 경우 "빠른"것보다 항상 느리게 진행됩니다. 루프가 있다면, 그들은 다른 속도로 루프를 통과 할 때 같은 요소를 가리킬 것입니다.
q=(q->next)?(q->next->next):q->next;
가하는 라인이 사전은 2로 빠른 포인터, 이 할 수있는 경우에 모든 것을
.이 목록의 끝 부분에 있기 때문에 할 수 없다면 하나씩 진행됩니다.
영어로,이 요소가 마지막이 아닌 경우 새 포인터를 다음 포인터 (NULL 일 수 있음)로 설정하십시오. 이 요소 이 마지막으로 인 경우 다음으로 설정하십시오. 은이됩니다.
나 자신, 내가로 작성한 것입니다 :
q=(q->next)?(q->next->next):NULL;
하지만 스타일의 문제입니다.
p은 각 반복마다 목록에서 한 단계 앞으로 항상 이동하지만, q은 두 단계 앞으로 이동합니다 (목록이 끝나지 않으면 q->next의 존재 여부 확인). 즉, 반복 할 때마다 q이 p보다 멀리 앞당겨집니다.목록에 루프가 없으면 q은 목록의 끝에 도달하기 만하면 루프가 종료됩니다. 이 루프 인 경우 일 경우 q이 결국 반복됩니다 (전달 속도가 빨라짐) p에 따라 잡습니다 (예 : p == q).
if (q-next) {
q = q->next->next; // Go forward two steps if possible
} else {
q = q->next; // Go forward one step otherwise
}
)
코드이 줄 :
q=(q->next)?(q->next->next):q->next;
은 다음과 같이 변경 될 수 있습니다.
q=(q->next)?(q->next->next):NULL;
목록이 끝나면 단순히 수표가됩니다. 그것이있는 경우 - 루프가없는 것보다.
http://stackoverflow.com/questions/3001695/how-to-determine-whether-a-linked-list-contains-a-loop-closed http://stackoverflow.com/questions/494830/의 중복 링크가있는 경우를 어떻게 결정할 것인가는 사이클을 사용하는 두 개의 메모리가있는 위치 http://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start -node-in-cycle-linked-list-work http://stackoverflow.com/questions/34249/best-algorithm-to-test-if-a-linked-list-has-a-cycle 및 대부분 : http : //stackoverflow.com/search? tab = 관련성 및 질문 = % 20if % 결정 20linked % 20list % 20has % 20a % 20cycle – dmckee