[HackerRank] Cycle Detection

https://www.hackerrank.com/challenges/detect-whether-a-linked-list-contains-a-cycle/problem

Cycle Detection | HackerRank

Data Structures > Linked Lists

 

연결 리스트의 head가 주어지면 해당 리스트가 순환 되는지 체크한다.

 

코드

bool has_cycle(SinglyLinkedListNode* head) {
   SinglyLinkedListNode* first = head, *second = head;
   if (!head) return false;
   while (first && first->next){
       first = first->next->next;
       second = second->next;
       if (first == second) return true;
   }
   return false;
}

 

설명

first와 second 노드를 각각 선언한다.

만약 head가 NULL이면 false를 리턴한다.

head가 NULL이 아니면, first와 first->next가 NULL이 아니라는 조건 하에 반복되는 while문을 실행한다.

first는 first->next->next로, second는 second->next로 지정해 속도를 다르게 하여 연결 리스트를 순회한다.

만약 first와 second가 일치하는 구간이 있다면 순환 구조를 가진 것이므로 true를 리턴한다.

while 루프가 끝나면 순환 구조를 찾지 못한 것이므로 false를 리턴한다.