速い指と遅い指で連結リストの輪を見つける｜コーディング面接問題

問題

連結リストの先頭の節 head を受け取ります。next をたどっていくと、いつか前に通った節へ戻ってくる (輪がある) なら真、最後の節にたどり着いて終わるなら偽を返す関数を書いてください。

各節は val (値) と next (次の節) を持ちます。Go の節は ListNode で、Val、Next と大文字で始まります
例の pos は、輪の作り方を表す数です。最後の節の next が、先頭から数えて pos 番 (0 から数える) の節へつながっています。pos が -1 なら輪はありません
pos は関数へは渡りません。 関数が受け取るのは head だけで、輪があるかどうかは節をたどって自分で見分けます
節の数は 0 以上 10000 以下、値はどれも -100000 以上 100000 以下です。違う節が同じ値を持つこともあります

例では、リストを先頭から読んだ値の並びと pos で書きます。

入力と出力の例

例 1

最後の 9 の次が、1 番の 7 へ戻ります。7、1、9 が輪になっています。

入力

head = [4, 7, 1, 9]
pos = 1

出力

true

例 2

輪がなく、2 で終わります。

入力

head = [6, 2]
pos = -1

出力

false

例 3

節が 1 つで、自分自身へつながっています。

入力

head = [3]
pos = 0

出力

true

面接での聞かれ方

連結リストの問題の中でも、よく出る 1 問です。

「連結リストに輪があるかを判定してください」
見た節を集合に覚える書き方を出すと、ほぼ必ず「追加のメモリを O(1) にできますか？」と続きます
書き終えたあとに「輪の入り口の節を返せますか？」「速い指は、なぜ遅い指を飛び越さずに必ず追いつくのですか？」と聞かれることもあります

ジュニアの問題なので、速い指が先へ進むときに空の節を読まない書き方と、追いつく理由を短く言えるかが見られます。

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

まず考える手順

段 1

まずは素直に、通った節を集合に覚えながらたどる書き方を考えます。同じ節に 2 回来たら輪があり、空にたどり着いたら輪はありません。時間は O(n) ですが、記憶も O(n) 使います。覚えるのは節そのもので、値ではありません。違う節が同じ値を持つことがあるからです。

段 2

記憶を使わずに見分けるため、指を 2 本使います。遅い指 slow は 1 つずつ、速い指 fast は 2 つずつ進めます。輪がなければ、速い指が先に空へたどり着きます。輪があれば、2 本とも輪の中へ入り、ぐるぐる回り続けます。

段 3

輪の中では、速い指は遅い指に 1 回ごとに 1 つずつ近づきます。差が 1 ずつ縮むので、飛び越すことはなく、輪の長さ以内の回数で必ず同じ節に重なります。そこで、2 本を進めたあとに同じ節かを比べ、重なったら真を返します。

段 4

速い指を進める前に、fast と fast.next の両方が空でないことを確かめます。どちらかが空なら、リストは終わっているので偽です。空のリストも、この確かめで最初に偽になります。

解答

Python

def has_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

JavaScript

function hasCycle(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;
}

Go

func hasCycle(
	head *ListNode,
) bool {
	slow, fast := head, head
	for fast != nil &&
		fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			return true
		}
	}
	return false
}

比べているのは値ではなく節そのもの (Python の is、JavaScript の ===、Go のポインタの ==) です。遅い指は速い指より後ろにいるので、速い指の確かめだけで、遅い指が空を読むことはありません。

計算量

時間は O(n) です。輪がなければ、速い指が節の数の約半分の回数で終わりに着きます。輪があれば、遅い指が輪に入るまでに n 回以内、入ってから重なるまでに輪の長さ以内の回数で済みます
使う記憶は O(1) です。指 2 本だけです
段 1 の集合の書き方も時間は O(n) ですが、記憶は O(n) です

よくある間違い

値を集合に覚える。 [5, 5, 5] のように同じ値が続くと、輪がないのに「同じ値に 2 回来た」として真を返します。覚えるのは節そのものです
fast.next を確かめずに 2 つ進める。 節の数が奇数のリストで、fast.next が空のまま fast.next.next を読み、止まります。条件は fast と fast.next の両方です
進める前に比べる。 2 本とも head から始めるので、進める前に比べると最初の 1 回で必ず重なり、輪がなくても真を返します。比べるのは進めたあとです
空のリストを見落とす。 head が空なのに head.next を読むと止まります。繰り返しの条件で fast を確かめていれば、最初に偽で抜けます

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日

def has_cycle(head): # 連結リストの節は val、next を持ちます。最後の next は None です # ここに書きます pass # 「実行」を押すと、この行の結果が出ます # build_list は並びから連結リストを組みます print(has_cycle(build_list([4, 7, 1, 9], 1)))

速い指と遅い指で連結リストの輪を見つける

問題