[리트코드] 141. Linked List Cycle / Javascript

문제주소 :https://leetcode.com/problems/linked-list-cycle/

Linked List Cycle - LeetCode

---

<문제 설명>

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.

 

Example 1:

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).

Example 2:

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.

Example 3:

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

 

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

 

Follow up: Can you solve it using O(1) (i.e. constant) memory?

 

<풀이법>

▒ 한줄 개념: 토끼와 거북이 알고리즘 ▒ 

단방향 연결리스트의 사이클 여부를 확인하는 문제이다. 여러 방법으로 시도하면서 문제를 풀어보았다.

 

1. 이미 방문한 value값 저장:

이미 방문한 노드의 value 값들을 배열에 저장하고, 새로운 노드에 진입할 때마다 이미 방문된 적이 있는 value값인지 확인해보았다. 하지만, 서로 다른 노드에 대해 동일 value값이 존재할 수 있는 문제이므로, 실패하였다.

 

2. 방문한 노드 자체를 저장:

방문한 노드의 value값이 아닌 노드 자체를 저장하였다. 방식은 1번과 동일하여, 문제를 통과하였다. 하지만 문제 맨 밑에 "O(1)의 공간복잡도 이하로 풀 수 있나요?" 라는 질문을 보고 다시 방법을 생각해보았다.

 

3. 토끼와 거북이 알고리즘:

혼자서는 생각이 안되어서 구글에 찾아보았고, 토끼와 거북이 알고리즘(Fast and Slow Algorithm / Tortoise and Hare Algorithm)을 알게되었다. 토끼와 거북이 알고리즘은 쉽게 말해, 거북이는 한 칸씩, 토끼는 두 칸씩 앞으로 이동한다. 만약 순환구조가 있다면, 어떻게든 둘이 만나게 될 것이니, 이를 통해 순환여부를 확인할 수 있다는 알고리즘이다.

 

토끼와 거북이 알고리즘을 사용하면, 거북이가 일직선으로 직진하는 동안 순환여부를 알 수 있으므로 시간복잡도는 O(N)이며, 두 개의 포인터(토끼, 거북이)만을 사용하여 정답을 알 수 있으므로 공간복잡도는 사실상 거의 없다고 볼 수 있다. 

 

아래는 토끼와 거북이 알고리즘을 이해하는데 도움이 된 블로그들이다.

https://heod.tistory.com/2

https://velog.io/@lacomaco/%ED%86%A0%EB%81%BC%EC%99%80-%EA%B1%B0%EB%B6%81%EC%9D%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-LeetCode-142

 

 

<코드(Javascript)>

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */

//토끼와 거북이 알고리즘(fast and slow algorithm)
var hasCycle = function(head){
    if(head === null) return false;
    
    let tor = head, hare = head;
    
    while(hare && hare.next){
        tor = tor.next;
        hare = hare.next.next;
        //console.log(tor, hare);
        if(tor === hare)
            return true;
        
    }
    return false;
}

// 가장 단순한 방법
// var hasCycle = function(head) {
//     const map = new Map();
//     while(head !== null){
//         if(!map.has(head)){
//             map.set(head, true);
//             head = head.next;
//         }else{
//             return true;
//         }
//     }
//     return false;
// };

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest