リンクリストの中央ノード取得
前半と後半に分けたい、という場面はよくあります。そこで最初に要るのが、真ん中がどこかという情報です。ところが札をたどる形のリストでは、これが素直に取れません。
長さを数えてから、もう一度半分だけ歩く
配列なら要素数がその場で分かるので迷いません。ところが札をたどる形のリストには、長さを聞ける相手がいません。数えるしかありません。
Python
n = 0
cur = head
while cur is not None:
n += 1
cur = cur.next
cur = head
for _ in range(n // 2):
cur = cur.next答えは合っています。ただ、同じ道を 2 回歩いています。しかも 1 周目が終わるまで、真ん中がどこかは 1 ミリも分かりません。長さが分からないまま真ん中に着く方法はないものか、という話になります。
2 周する書き方が悪いわけではありません。件数が少なければ差は出ませんし、読みやすさはむしろ上です。ただ「数えてから戻る」しか手が無いと、長さを聞けない相手を渡されたときに思考が止まります。
2 倍の速さで歩くほうが端に着いたとき
サイクル検出で使った 2 つの目印を、そのまま持ってきます。片方は 1 歩、もう片方は 2 歩です。
Python
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next速いほうが k 回進んだとき、進んだ距離は 2k です。それが端に届いたということは、2k がほぼ全長ということです。すると遅いほうがいる k は全長のおよそ半分になります。歩き終わった瞬間、slow が真ん中に立っています。1 周で済みました。
止める条件で確かめているのは、2 歩ぶんの余地があるかどうかです。1 歩ぶんしか見ずに 2 つ動かすと、末尾の先へはみ出します。ノードなら空に next を聞いて落ち、番号で持つなら範囲外を読みます。境界の確認を 2 つ分書く必要があるのは、そのためです。
真ん中が 2 つあるとき、どちらを返すか
長さが奇数なら真ん中は 1 つに決まります。偶数のときは 2 つあり、どちらになるかは止め方で変わります。
| 長さ | 進んだ回数 | slow がいる位置 |
|---|---|---|
| 5 | 2 | 3 番目 |
| 4 | 2 | 3 番目 |
| 2 | 1 | 2 番目 |
| 1 | 0 | 1 番目 |
今回の課題は、偶数のとき後ろ側を返す決まりです。[1, 2, 3, 4] なら 3 になります。前側が欲しい仕様のときは、止める判定を 1 つ手前に置きます。仕様として先に決めておかないと、テストが偶数長のときだけ落ちて、原因が見えにくくなります。
真ん中が要る場面を具体的に見ておきます。並べ替えのために 2 つに割るとき、割る位置がずれると片方だけが長くなり、段数が増えて遅くなります。回文かどうかを調べるときは、前半と後半の長さがそろっていないと比較そのものが噛み合いません。真ん中を正確に取れることが、その先の処理の前提になっています。
なお長さが 1 のときは、1 度も進まずに先頭がそのまま答えです。書いた条件がこの場合に 1 回でも回らないか、手で確かめておいてください。
要件
- 連結リストは配列 arr (長さ 1 以上) で表現する
- slow / fast 2 ポインタ法を使って 1 パスで取得すること
- 偶数長のときは後ろ側の中央を返す (例: [1,2,3,4] -> 3)
入出力例
middleNode([1,2,3,4,5]) → 3
middleNode([1,2,3,4]) → 3
middleNode([1]) → 1
middleNode([1,2]) → 2
middleNode([10,20,30]) → 20
middleNode([1,2,3,4,5,6]) → 4ヒント
