LC 141-Linked List Cycle

문제

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

예시

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

풀이

• 링크드 리스트의 순환 여부를 검사하는 문제이다.
• 우선 head가 비어있으면 순환할 노드가 없으므로 false를 반환한다.
• 링크드 리스트가 순환한다는 것은 모든 노드의 next가 null이 될 수 없다는 것과, 맨 끝 노드의 next가 이미 지나온 노드를 가리킨다는 것을 의미한다.
• 링크드 리스트 내부를 두 칸 씩 뛰어넘는 runner와 한 칸 씩 전진하는 walker를 두면, 리스트가 순환 구조라고 했을 때 언젠가는 runner가 walker와 같은 노드에 멈출 때가 온다.

코드

var hasCycle = function(head) {
    if (!head) return false;

    let walker = head;
    let runner = head;

    while (runner) {
        if (!runner.next) return false;

        runner = runner.next.next;
        walker = walker.next

        if(runner === walker) return true;
    }
    return false;
};