[Leetcode][자바스크립트][Easy] 141. Linked List Cycle

풀이1

 

/**
 * 141_LinkedListCycle.js
 * Easy
 * https://leetcode.com/problems/linked-list-cycle/
 */

const nodeArr = [];
var hasCycle = function(head) {
    if (head === null || head.next === null) return false;
    if (nodeArr.indexOf(head.next) > -1) return true;
    nodeArr.push(head.next);
    return hasCycle(head.next);
};

 

문제 예시에서 input 이 배열로 주어지는 것처럼 나타나서 처음에 좀 헷갈렸다. 

hasCycle 함수 자체를 재귀로 놓고 돌렸는데 그 결과로 nodeArr 배열이 함수 밖으로 나가면서 위험해졌다. 

 

풀이2

 

/**
 * 141_LinkedListCycle.js
 * Easy
 * https://leetcode.com/problems/linked-list-cycle/
 */
 
 var hasCycle = function(head) {
    const nodeArr2 = [head];
    let currNode = head;
    while(true) {
        if (currNode === null) break;
        currNode = currNode.next;
        if (nodeArr2.indexOf(currNode) > -1) return true;
        nodeArr2.push(currNode);
    }
    return false;
}

 

while 로 linked list 를 head를 시작으로 끝까지 루프를 돌면서 확인하는 방식으로 변경했다. nodeArr2 배열에 모든 node 에 대한 참조를 넣어두고 새로운 node.next 가 이미 가진 nodeArr2 배열의 참조 중에 존재하면 cycle 이 존재한다는 뜻이다. 

 

풀이3 - 풀이2 최적화

 

/**
 * 141_LinkedListCycle.js
 * Easy
 * https://leetcode.com/problems/linked-list-cycle/
 */
 
 var hasCycle = function(head) {
    const nodeSet = new Set();
    let currNode = head;
    while(currNode !== null) {        
        if (nodeSet.has(currNode)) return true;
        nodeSet.add(currNode);
        currNode = currNode.next;
    }
    return false;
}

 

방식은 풀이2와 동일하다. nodeArr2 배열 대신 Set 을 활용하고, currNode === null 일 때 break 하던 방식에서 while 안에 조건문이 들어갔다. indexOf 가 아닌 has() 를 사용해 확인 가능해졌다. 코드도 훨씬 깔끔하고 빠르다. 

 

Test를 위한 helper 함수 추가

 

/**
 * 141_LinkedListCycle.test.js
 * @param {ListNode} head
 * @return {boolean}
 */

const { hasCycle } = require('./141_LinkedListCycle');
const { makeSinglyLinkedListFromArray } = require('../../../../Preset/LinkedList/LinkedList.helper');

test('head = [3,2,0,-4], pos = 1 => true', () => {
    const head = makeSinglyLinkedListFromArray([3,2,0,-4], 1);
    expect(hasCycle(head)).toBe(true); 
});


test('head = [1,2], pos = 0 => true', () => {
    const head = makeSinglyLinkedListFromArray([1, 2], 0);
    expect(hasCycle(head)).toBe(true);    
});

test('head = [1], pos = -1 => false', () => {
    const head = makeSinglyLinkedListFromArray([1], -1);
    expect(hasCycle(head)).toBe(false);    
});

 

위의 테스트를 진행하기위해선 테스트에 쓰일 cycle 이 존재하거나 존재하지 않는 singly linked list 를 생성해야한다. Value를 가진 배열과 tail의 next에 연결할 Index position 을 넘기면 그에 해당하는 연결리스트를 만드는 function 을 아래와 같이 만들었다.

 

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

/**
 * @param {Array} arr 
 * @param {Index Number} tailNextPos 
 * @returns 
 */
function makeSinglyLinkedListFromArray(arr, tailNextPos) {
    const len = arr.length;
    let head, tail, curr;
    arr.forEach((val, idx) => {
        const node = new ListNode(val);
        if (idx === 0) head = node;
        if (idx === len - 1) tail = node;
        if (curr) curr.next = node;
        curr = node;        
    });

    if (tailNextPos > -1 && tailNextPos < len) {
        let tmp = head;
        for (let i = 0; i <= tailNextPos; i++) {
            tmp = head.next;
        }
        tail.next = tmp;
    }

    return head;
}