[HackerRank] Cycle Detection

# Cycle Detection (Linked Lists)

[문제]

 

[코드]

bool has_cycle(SinglyLinkedListNode* head) {
    if(head == NULL) return 0;
    
    SinglyLinkedListNode* fast = head;
    SinglyLinkedListNode* slow = head;
    
    while(fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
        
        if(fast == slow) return 1;
    }
    return 0;
}

 

[코드설명]

Linked List에서 cycle의 유무를 확인하는 문제다.

두 개의 포인터를 만들고, 하나는 +1만큼 다른 하나는 +2만큼 링크를 따라 이동시켰다.

두 포인터의 이동 간격이 +1 차이 나기 때문에 list에 cycle이 존재한다면 두 포인터가 n바퀴를 돌아 같은 노드에서 만나기 때문이다.

(하나의 포인터를 고정시키고 다른 하나를 +1만큼 이동시켰을 때 n바퀴를 돌아 같은 노드에서 만나는 것과 동일한 원리)

 

따라서 위 코드에서 fast==slow라면 cycle이 존재하는 것이다.

그렇지 않고 한 포인터가 NULL이 된다면 cycle이 존재하지 않는다는 의미이므로 while문을 종료하고 0을 반환한다.

 

[채점 결과]