[Leetcode] 141. Linked List Cycle

Identifying the Problem

주어진 linked list가 무한 순회하는지 판단한다.

Organizing thoughts

 
<정답 참조했음>

비유를하자면 제논의 역설과 비슷하다.
운동장을 육상선수와 내가 돌고, 육상선수가 나보다 2배 빠르다고 했을 때, 
둘이 언젠가 만나는 지점이 있음

이 문제에선 그 지점을 찾으면 된다.

Sourcecode

bool hasCycle(struct ListNode *head) {
    
    struct ListNode *slow, *fast;
    
      
    
    if(!head || !(head->next)) //노드의 수가 1개 이하인 경우 false 리턴
        return false;
        
    slow = head->next; //2번째 노드
    fast = head->next->next; //3번째 노드
    
    while(fast && fast->next)
    {
       if(slow == fast) return true; //처음과 끝이 같아지는 지점
        
       slow = slow->next; 
       fast = fast->next->next; //slow의 2배속도로 탐색한다. 
    
            
    }
    
     return false;
}

 

New things learned

• 하나의 배열에 탐색 index를 여럿두면 배열 여러 개를 복사한 효과를 낸다.