LeetCode / Linked List / 142번 / Linked List Cycle II / JS

< 문제 바로가기 >

Linked List Cycle II - LeetCode

 

< 문제 간단설명 >

순환을 할 수도 있고, 순환하지 않을 수도 있는 Linked List가 주어진다.

만약 어딘가의 위치에서 순환이 이루어지고 있는 Linked List 라면, 순환이 이루어지고 있는 cycle 에서의 첫번째 노드를 반환해주면 되는 문제이다.

만약 순환이 없는 Linked List 라면 null을 반환해주면 된다.

 

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let listNodeSet = new Set();

    while(head) {
        if(listNodeSet.has(head)) {
            return head;
        }
        listNodeSet.add(head);
        head = head.next;
    }

    return null;
};

---

모든 Linked List의 노드를 순회하면서 Set에 노드 자체를 넣어준다.

만약 cycle이 생기는 구간에 진입을 하면, cycle의 맨 마지막의 다음은 cycle의 맨 처음 노드일 것이다.

하지만 cycle의 맨 처음 노드는 cycle을 돌기전에 이미 한번 Set에 들어가있을것이다.

따라서 이미 Set에 있는 노드라면 그 노드를 반환을 해주면 된다.