[LeetCode] 141. Linked List Cycle, Easy

1. 문제

• 연결 리스트의 head가 주어질 때, 해당 리스트 내 사이클이 존재하는 지 true 또는 false를 반환하라.
• pos는 전달되지 않는 값이다.

2. 해결

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function hasCycle(head: ListNode | null): boolean {
    let faster = head, slower=head;
        
    while(faster && faster.next) {
        faster = faster.next?.next;
        slower = slower.next;
        
        if(faster === slower) {
            return true;
        }
    }
    
    return false;
};

• 플로이드 토끼 거북이 알고리즘을 사용하면 된다. 토끼는 2칸씩 이동하고 거북이는 1칸씩 이동하게 하면, 사이클이 있는 경우 두 포인터는 언젠가 만나게 된다.
• 사이클이 없는 경우, 거북이 포인터는 중간 노드에서 멈추게 된다. 관련 문제.

https://fbtmdwhd33.tistory.com/295

[LeetCode] 876. Middle of the Linked List, Easy