[Easy] 141. Linked List Cycle

Leetcode 141번 문제는 주어진 Linkedlist에 cycle ,즉 순환인 발생하는지 알아내는 문제이다. 위의 예제처럼 어느 한 노드에서 뒤에 노드로 뒤돌아가 반복된다면 cycle이 발생한 것이므로 true를 return 하면 된다. 

 

#풀이

• Hashset을 사용한 풀이

public class Solution {
    public boolean hasCycle(ListNode head) {
        HashSet set = new HashSet();
        boolean isCycle = false;
        while(head != null){
            isCycle = set.add(head);
            head = head.next;
            if(!isCycle){
                return !isCycle;
            }
        }
        return !isCycle;
    }
}

Set의 특성은 중복 데이터가 있으면 안 된다는 것이다. 그러니 각 노드를 set에 추가하며 linkedlist를 순회하면서, 만약 set.add가 false가 되는 순간이 있다면, 그건 중복이 발생했다는 뜻이다, 즉 cycle이 발견됐다는 뜻 이기 도하다. 그러므로 true를 return 해주면 된다.  

 

• Floyd's Tortoise and Hare Algorithm (플로이드의 토끼와 거북이 알고리즘)

public boolean hasCycle(ListNode head) {
    if(head==null) return false;
    ListNode walker = head;
    ListNode runner = head;
    while(runner.next!=null && runner.next.next!=null) {
        walker = walker.next;
        runner = runner.next.next;
        if(walker==runner) return true;
    }
    return false;
}

다음 방법은 플로이드의 토끼와 거북이 알고리즘을 사용한 방법이다. 이 방법은 거북이, 즉 노드를 하나씩 지나다니는 reference 이고, 토끼 즉 두 개의 노드를 한번에 지나다니는 reference를 사용한다. 만약 이 두 개의 reference들이 똑같은 노드를 가리키게 되면 그 연결 리스트에 순환이 발생했다는 뜻이 되기에, true를 return 시키면 된다.

플로이드의 토끼와 거북이 알고리즘