[자료구조] Linked list - 2

141. Linked List Cycle

🤔 문제 이해

연결리스트가 순환이 되는지 확인 있으면 true, 아니면 false반환

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
  
};

🤔 EX

입력: head = [3,2,0,-4], pos = 1 출력: true

입력: head = [1,2], pos = 0 출력: true

🤔 의사 코드 

let slow = head 두 개의 포인터인 slow와 fast를 초기화
let fast = head 둘 다 링크드 리스트의 시작점인 head를 가리킵니다.

while (fast != null && fast.next !== null)
{ fast 포인터가 끝에 도달하지 않았고, 다음 노드도 존재하는 동안 반복
이 조건은 fast 포인터가 null,fast.next가 null이면 반복문을 종료

slow = slow.next; slow 포인터를 한 칸씩 전진시킵니다.
fast = fast.next.next; fast 포인터를 두 칸씩 전진시킵니다.

if (slow === fast) {: slow와 fast 포인터가 만나면 사이클이 존재 true를 반환
return false;: 반복문을 모두 돌았지만 사이클이 없는 경우

즉 slow와 fast 포인터가 만나지 않은 경우 false를 반환합니다.

🤔 해결한 코드

var hasCycle = function(head) {
    let slow =head
    let fast = head
    while(fast!=null && fast.next!==null){
        slow= slow.next
        fast = fast.next.next

        if(slow ===fast){
            return true
        }
    }
    return false
};

🤔 Thinking

linked list 코테 문제중에서 제일 기본이 되는 문제인것같았다.

구조적으로는 어렵지않았지만, 이론으로는 공부한적 있지만 실제로 linked list를 코드를 통해서 접해본건 처음이였기에 좀 어렵다고 느껴졌다. 조금더 기초적인 관련 문제나 코드들을 보며 공부해야 될것같다. 다음 문제에서 아마 하고있을듯