BFE.devでのAI解答例 - JavaScript コーディング問題
100. linked listにcircleあるかのチェック

function hasCircle(head: Node): boolean {  let fast: Node = head  let slow: Node = head    while (fast && fast.next) {    fast = fast.next.next    slow = slow.next        if (fast === slow) {      return true    }  }    return false}

この関数では、スローポインタとファストポインタを使ってリストをトラバースします。ファストポインタは2つのノードを移動し、スローポインタは1つだけ動きます。もしファストポインタがリストの末尾に達した場合、もしくはファストポインタがスローポインタを追いついた場合、circleが存在すると言えます。

この関数の時間複雑度はO(n)で、空間複雑度はO(1)です。

空間複雑度がO(1)の解決方法としては、フラグを立てて、リスト内の各ノードを訪問するたびにそれを訪問済みとしてマークする方法があります。しかし、この方法ではリストの長さによっては、大量のメモリが必要になりうるため、あまり効率的ではありません。