solution 1

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    // 마지막 node가 next에 담은 값을 통해 
    // pos 인덱스에 있는 node로 접근할 수 있으면 순환

    if(head === null){
        return false;
    }

    // 앞에서부터 연산이 진행되면서 한번 지났던 head를 저장
    // 저장된 head가 다시 나오면 순환 구조
    let map = new Map();

    while(head.next !== null){
      	// 처음 지나는 node라면 map에 저장
        if(!map.has(head)){
            map.set(head, true);
          
          	// 다음 head로 이동한다.
            head = head.next;
            continue;
        }

      	// 처음 지나는 node가 아닌 곳으로 왔다면
      	// 순환이 발생한 것이므로 true 반환
        return true;
    }

    return false;
};

문제가 어렵다기보다는 Linked List를 어떻게 사용하는지를 몰라서 많이 헤맸다.
head가 배열로 들어오는 줄 알았더니, 전혀 다른 방식의 사용법을 가지고 있었다.

문제에서 요구하는 것은 주어진 Linked List에 cycle이 존재하는지 판단하는 것이다.
이를 판단하는 것은 간단하다.
마지막 node의 next가 이미 거쳐왔던 node 중 하나를 가리키고 있다면 cycle이 존재하는 것이다!

이 풀이는 시간 복잡도가 최상위권이었으나, 공간 복잡도가 최하위권이었다.
아무래도 Map 객체를 사용하는 것이 문제였던 것 같다.
그 외에는 아무것도 사용하지 않았는데도 이정도인 것을 보니, 연산하는 또 다른 방법이 있는 것 같다.

찾아보니, Linked List에서 순환 구조를 알아내는 알고리즘이 있었다.
따라서, Floyd's Cycle Detection Algorithm을 사용해서 문제를 해결해보고자 한다.

solution 2

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    // 마지막 node가 next에 담은 값을 통해 
    // pos 인덱스에 있는 node로 접근할 수 있으면 순환

    if(head === null){
        return false;
    }

    // 토끼와 거북이를 설정.
    // 거북이는 첫 node, 토끼는 그보다 1칸 앞에서 시작한다.
    let rabbit = head.next;
    let turtle = head;

    // rabbit이 null이면 node가 1개밖에 없는 상황이므로 순환이 아니라 while문을 실행하지 못함.
    // 문제는..node가 여러 개이면서 순환 구조가 아닌 경우에는 연산 도중에 node가 null로 나와서
    // rabbit을 재연산하는 과정에서 런타임 에러가 발생함. 이에 대한 처리가 필요!
    while(rabbit !== null){
        // 토끼와 거북이가 같은 node에 있으면 순환이 있는 것.
        if(rabbit === turtle){
            return true;
        }

        // 만약 rabbit의 다음이 있다면
        if(rabbit.next){
            // 토끼는 2칸, 거북이는 1칸씩 이동한다.
            rabbit = rabbit.next.next;
            turtle = turtle.next;
            continue;
        }

        // 다음이 없다면 순환 구조가 아니다.
        break;
    }

    return false;
};

방금 말한 알고리즘은 토끼와 거북이 알고리즘으로도 알려져 있다.
거북이는 첫 번째 node부터 시작해서 한 칸씩 순회하고,
토끼는 두 번째 node부터 시작헤서 두 칸씩 순회한다.
거북이와 토끼가 만나게 된다면 이 Linked List는 cycle을 가지고 있다는 것이다.

그런데, 이 말만 들으면 rabbit.next.next를 해서 토끼가 2칸 이동할 수 있는지 없는지를 판단하면
간단하게 해결될 것 같지만 그렇지 않다.

만약 rabbit.next가 null인 경우라면 null.next가 되므로 런타임 에러가 발생하기 때문이다!

따라서, 바로 rabbit.next.next로 2칸 뒤를 찾으려고 하면 안되고,
먼저 rabbit.next를 통해 1칸 뒤 node의 존재를 확인해야한다.
1칸 뒤에 node가 있다면 그 다음 노드가 있든 없든 런타임 에러를 방지할 수 있고,
없으면 rabbit.next.next는 null이 되고, 있으면 2칸 뒤의 node가 할당되므로
문제없이 해결해나갈 수 있다.

이 알고리즘을 적용하는 것으로 메모리 성능은 끌어올릴 수 있었다.
하지만 시간 복잡도는 오히려 하락한 모습을 보인다.

다른 분의 solution

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let p1 = head
    let p2 = head
    
    while (p2 && p2.next && p2.next.next) {
        p1 = p1.next
        p2 = p2.next.next
        
        if (p1 === p2) {
            return true
        }
    }
    
    return false
};

다른 분들도 마찬가지로 Floyd's Cycle Detection Algorithm을 사용하셨다.
그 중에서 코드가 가장 깔끔한 분의 풀이를 가져와봤다.
필자가 설명했던 부분을 while의 조건에 함께 부여해서 불필요하게 while이 진행되지 않도록 만들었다.

그러나 역시 시간 복잡도는 필자의 첫 번째 풀이가 가장 빨랐다.
알고리즘을 익혔다는 것에 의미를 두는 것이 좋겠다.