Linked List Cycle

💬 문제

[문제 링크]

연결 리스트의 시작 노드 head
해당 연결 리스트에 cycle이 존재한다면 true
아니라면 false 반환

✍️ 나의 풀이

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    while (head) {
        if (head.visit)
            return true;
        head.visit = 1;
        head = head.next;
    }

    return false;
};

head 부터 시작하여 노드(객체) 내에 visit 멤버 변수를 추가
this.next를 이용하여 다음 노드로 이동
이미 방문을 해서 visit이 존재한다면 cycle이 생겼으므로 true 반환
next가 null이어서 그대로 순회가 끝났다면 false 반환

📌 결과

Accepted
Runtime 57ms (Beats 88.51%)
Memory 52.31MB (Beats 93.00%)

📚 러닝 포인트

연결리스트 문제가 시작되었다. 첫번째 문제라 그런지 매우 쉬워서 금방 해결할 수 있었다. 다른 사람들은 어떻게 구현했나 둘러보았는데, 대부분 slow와 fast 두 가지 포인터를 사용해서 slow는 한 칸씩 전진, fast는 두 칸씩 전진하여 둘이 같아졌을 때 cycle이 생겼음을 확인했다. 내 코드는 cycle이 생기는 노드까지 하나씩 확인하면서 가야되는데 해당 방식은 두 개씩 건너뜀으로써 더 빠르게 발견할 수 있었다..!