[해커랭크] Cycle Detection [JAVA]

문제링크: www.hackerrank.com/challenges/detect-whether-a-linked-list-contains-a-cycle/problem

Cycle Detection | HackerRank

처음에 문제를 보고 입력값 범위가 안주어져서 어떻게 풀어야하나 싶었다.

적당한 값으로 갱신하면서 탐색중에 갱신된 그 값을 발견할 경우 싸이클이 있다고 판단해봤는데

통과됐다. 잘못됐다고 생각하고 다른 사람의 풀이를 참고했더니 창의적인 아이디어가 있었다. 

 

*잘못된 풀이

    // Complete the hasCycle function below.

    /*
     * For your reference:
     *
     * SinglyLinkedListNode {
     *     int data;
     *     SinglyLinkedListNode next;
     * }
     *
     */
     
    
     
    static boolean hasCycle(SinglyLinkedListNode head) {
        while(true){
            if(head==null){
                return false;
            }
            if(head.data== -987654321) return true;
            head.data = -987654321;
            head = head.next;
        }

    }

*다른 사람풀이 (copy)

int HasCycle(Node head) {
    if (head == null){
        return 0;
    }

    Node slow = head;
    Node fast = head;

    while (fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast){
            return 1;
        }
    }

    return 0;
}