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)の解決方法としては、フラグを立てて、リスト内の各ノードを訪問するたびにそれを訪問済みとしてマークする方法があります。しかし、この方法ではリストの長さによっては、大量のメモリが必要になりうるため、あまり効率的ではありません。