【LeetCode in TypeScript】141.Linked List Cycle

問題

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.

headが与えられたとき、そのリンクリストにサイクルが存在するかどうかを判定せよ。

リンクリストにサイクルがあるとは、リスト内のあるノードに、次のポインタをたどることで再び到達できる場合を指す。内部的には、tailの次のポインタがどのノードに接続されているかを示すためにposが使われる。ただし、posは引数として渡されない。

サイクルが存在する場合はtrueを返し、そうでない場合は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.

解答

function hasCycle(head: ListNode | null): boolean {
    const check = new Set<ListNode | null>()
    let res: boolean = false
    
    while (head && !res) {
        check.has(head) ? res = true : check.add(head)
        head = head.next
    }
    return res
}

解説

この問題は、リンクリストにサイクルがあるかどうかを判断する問題です。サイクルが存在する場合、あるノードに再び到達できることになります。サイクルがない場合は、リストの終端に到達します。

ハッシュセットを使用するアプローチ

• リストを一つずつ進めながら、ノードをハッシュセットに追加していく
• もし、現在のノードがすでにハッシュセットに存在する場合、サイクルがあると判断できる
• リストの終端に到達した場合、サイクルは存在しないと判断する
• このアプローチの時間計算量はO(n)であり、空間計算量もO(n)
  ※ノードの数だけハッシュセットに保存するため

---