[HackerRank] Cycle Detection

Cycle Detection | HackerRank

Cycle Detection | HackerRank

 

 

<문제>

이 문제는 리스트가 순환되는지 아닌지를 알려준다.

input: 한 리스트를 입력받는다.

output: 리스트가 순환되면 1, 아니면 0을 리턴한다.

 

<코드>

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

 

<풀이>

tmp1과 tmp2 노드 포인터를 선언해서 각자 처음에는 head를 가리키도록 하였다. 만약 head가 null이면 false를 리턴하고, null이 아니면 while 반복문을 통해 tmp1포인터는 tmp1->next->next해서 2개씩 확인하고, tmp2는 tmp2->next해서 1개씩 확인하도록 하였다. while 반복문을 돌다가 tmp1이랑 tmp2가 같으면 순환하는 것이므로 true를 리턴하고, 아니면 false를 리턴하여 문제를 풀 수 있었다.

 

<실행결과>