LeetCode - 141. Linked List Cycle (JavaScript)

Easy, Graph - Cycle

RunTime : 65 ms / Memory : 53.95 MB

문제

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.

풀이

1. Set()을 이용한 Hash Table 기반 풀이

• 현재 위치한 노드 값을 visited에 add하고, 다음 노드로 순회한다.
• 이미 visited에 있다면 true,
  null을 마주한다면(더이상 연결되지 않음) false

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
var hasCycle = function (head) {
  let visited = new Set();
  let cur = head;

  while (cur !== null) {
    if (visited.has(cur)) {
      return true;
    }
    visited.add(cur);
    cur = cur.next;
  }

  return false;
};

2. Two-pointer를 이용한 풀이

• cyclic graph를 판단할 때 기존에 접해보지 않았던 풀이법이라 남긴다.
• 두 포인터를 준비한다.
  • 하나는 한 칸씩(slow.next), 나머지 하나는 두 칸씩(fast.next.next) 이동한다.
• 만약 두 포인터의 접점이 발생한다면 해당 그래프는 사이클이 존재

var hasCycle = function(head) {
    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;         // slow는 한 칸 이동
        fast = fast.next.next;    // fast는 두 칸 이동

        if (slow === fast) {
            return true; // slow와 fast가 만나면 사이클이 존재
        }
    }

    return false;
};