[알고리즘] LeetCode Linked List Cycle JS

개요

연결리스트의 맨 마지막이 노드와 연결되어있는지, 즉 원형 연결 리스트인지 확인하는 문제이다.

Linked List Cycle - LeetCode

 

 

풀이

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  let node = head;
  const map = new Map();

  while (node) {
    if (map.has(node)) return true;
    map.set(node, 1);
    node = node.next;
  }

  return false;
};

지나간 노드들을 해쉬로 저장하고 탐색하는 방식으로 구현했더니 풀리긴 했다.

 

그런데 뭔가 문제에서 해결하고자하는 방식이 아닌거 같아서 다른 사람의 풀이를 참고했다.

 

DISCUSS

const hasCycle = (head) => {
  let fast = head;
  while (fast && fast.next) {
    head = head.next;
    fast = fast.next.next;
    if (head === fast) return true;
  }
  return false;
};

보통 연결리스트를 풀때는 투포인터를 많이 활용하는 거 같다.

 

먼저간 노드는 원형이라면 반드시 head를 잡을 수 있게 된다

 

위 코드를 확인해보면 fast가 움직이면서 head와 만난다면 원형 리스트가 되는 것이니 true를 리턴하고 fast가 null이 되버리면 끝에 도달한게 되니 false가 된다.