Pythonのリンクリスト面接で必須の反転・マージ・高速低速・ダミーノード・サイクル検出を実例で整理。初見問題でも崩れない解き方を身につけたい方は必見です。
リンクリストで苦戦する候補者の多くは、概念を知らないからつまずいているわけではありません。各ノードが値と次のノードへのポインタを持つノードの連鎖がリンクリストだということは理解しています。問題は、Python のリンクリスト面接では、その概念を使って何かをしなければならない点です。制限時間の中で ListNode クラスをゼロから書き、参照を一つも失わずにリストを反転し、面接官の忍耐が尽きる前にサイクルを検出する。これは定義を知っていることとは別のスキルであり、ほとんどの学習リソースはその二つを同じものとして扱っています。
このガイドは、ノード構造の理解から、面接官が実際に何度も出すパターンを実行できるようになるまでの最短ルートです。あり得るすべてのリンクリスト問題を網羅するわけではありません。重要な問題、圧力のかかる場面でも崩れないテンプレート、そして一見正しそうな解答を静かに壊してしまうミスを扱います。
Python におけるリンクリストの正体と、なぜ面接官が何度も聞くのか
インデックスで考えるのをやめて、ノードで考える
配列は位置を与えてくれます。インデックス 3 を指定すれば、インデックス 3 の値が得られる。定数時間で、移動は必要ありません。リンクリストは参照を与えてくれます。先頭から始めて、必要な場所に着くまでポインタをたどります。この違いは些細な話ではありません。面接官がリンクリストを持ち出す理由そのものです。
面接官が二つの構造を比較させるとき、彼らはそのトレードオフがなぜ存在するのかを理解しているかを見ています。配列は連続したメモリに配置されるため、ランダムアクセスが速く、キャッシュの挙動も予測しやすくなります。リンクリストはノードがメモリ上に散らばるため、ランダムアクセスのための走査は遅くなりますが、正しいポインタさえ持っていれば任意位置への挿入・削除は O(1) になります。なぜなら、要素をずらすのではなく、参照を付け替えているだけだからです。 MIT OpenCourseWare のデータ構造ノートによれば、これらの時間計算量の差は、言語実装の違いではなく、基礎となるメモリモデルに直接由来します。
「配列よりリンクリストを使うのはどんなときですか?」という面接質問には、ちゃんとした答えがあります。シーケンスの途中で頻繁に挿入・削除を行い、ランダムアクセスが不要なときです。率直に言えば、Python の本番コードでは多くの場合、手書きのリンクリストより `collections.deque` のほうがうまく扱えます。それでも面接では、実運用で使うかどうかではなく、そのトレードオフを理解しているかが見られています。
実際にはどう見えるか
Python で 3 要素の配列をたどるのは一行です。`arr[2]`。3 ノードのリンクリストをたどるには、3 回ポインタを辿る必要があります。`head`、次に `head.next`、そして `head.next.next` です。ランダムアクセスでは遅いので、遅く感じるのではなく実際に遅いのです。では、ノード 1 と 2 の間にノードを挿入したいとしましょう。配列なら、位置 1 より後ろの要素をすべて 1 つ右にずらします。O(n) です。リンクリストなら、ポインタを 2 本付け替えるだけです。正しいノードにたどり着いていれば O(1) です。
この違いが腑に落ちたのは、「これは何番目のインデックスか?」ではなく、「このノードは何を指しているのか?」と考えるようになってからでした。リストは壊れた配列ではなくなり、連鎖の形そのものが構造だと見えるようになったのです。そう見えるようになると、ポインタ操作が恣意的ではなくなります。
面接で実際に使える ListNode テンプレートを書く
余計な工夫をしない、最小限のコンストラクタ
面接で書く ListNode クラスは、すぐ読めて、30 秒以内で টাইピングできるものであるべきです。使える形はこれです。
これだけです。`val=0` と `next=None` をデフォルトにしておけば、値だけでノードを作ることも (`ListNode(5)`)、インラインで連結することも (`ListNode(1, ListNode(2, ListNode(3)))`) できます。どちらのパターンも頻繁に出ます。デフォルト値があることで、コンストラクタの柔軟性を保ちながら、思考コストを増やしません。
二重連結リスト変種のために `prev` ポインタを追加する候補者もいます。問題文で明示的に求められていない限り、追加しないでください。不要な属性は、丁寧さではなくノイズのサインです。
slots は良い小ネタですが、本質ではありません
クラス定義に `__slots__ = ('val', 'next')` を追加すると、Python はインスタンスごとの `__dict__` ではなく固定サイズのメモリレイアウトを使うようになります。大量に生成される ListNode では、メモリオーバーヘッドを目に見えて減らせます。`__slots__` に関する Python ドキュメント に仕組みの詳細があります。
面接では、`__slots__` に触れること自体は Python のオブジェクトモデルを理解しているサインとして妥当です。ただし、求められていないのにテンプレートへ書き込むのは別問題です。面接官はその行について説明を求める可能性が高く、きれいに説明できなければ、入れないほうがましです。知識としては押さえておき、メモリ最適化について聞かれたら使えばよいのであって、最初から前面に出す必要はありません。
実際にはどう見えるか
このテンプレートで 3 ノードのリストを作成し、たどる例です。
走査パターン — `current = head` から始めて、`current = current.next` で進み、`current` が `None` になったら止める — は、これから書くほぼすべてのリンクリスト解法の背骨です。何より先に、このループを身体で覚えてください。
派手なパターンに触る前に、走査・挿入・削除・反転を覚える
走査は地味ですが、他のすべてを救う基礎です
高速/低速ポインタやサイクル検出にいきなり飛びつくリンクリスト対策は、砂地の上に家を建てるようなものです。走査はウォームアップではありません。ほかのパターンすべてが依存する基礎操作です。走査の途中で `current` を見失えば、リストを失います。頼れるインデックスはありません。
先ほどの走査ループが、そのままパターン全体です。知っておく価値がある変化は、削除と反転で必要になる `prev` と `current` を同時に管理する二ポインタ走査だけです。先に進む前に、両方に慣れておいてください。
一つのポインタだけで済ませようとして削除を壊す典型例
典型的な削除バグはこうです。候補者が `current.next = current.next.next` と書いたあと、`current.next` をもう一度使おうとしてしまうのです。すでにその参照が消えていることに気づいていません。修正はいつも同じです。付け替える前に、必要なものを保存します。
これは繊細なバグではありません。候補者が急いでいて、ポインタの状態を口に出さなくなったリンクリスト演習のほぼすべてで現れます。対策は、声に出して状態を述べることです。「`next` を再代入する前に保存します」と言えばよいのです。
実際にはどう見えるか
反復的な反転は、単独で最も重要な操作です。手順を一つずつ追ってみましょう。
各ステップで、`next_node` は `current.next` を上書きする前に保存されています。たったこの一行、前方参照を保存することが、きれいな反転と、リストが `None` の中に消えてしまうことの分かれ目です。なぜ保存が必要なのかを一度理解すれば、挿入と削除も同じ種類の理屈で納得できるようになります。
面接官が何度も確認する 5 つのリンクリストパターン
反転、マージ、高速/低速、ダミーノード、サイクル — ゲームはこの 5 手で決まる
Python のリンクリスト面接問題は、表面上は多様に見えます。しかし本質はそうではありません。ジュニア〜ミドルレベルの面接で遭遇するほぼすべての問題は、次の 5 つの基本パターンの変形です。反転、ソート済み 2 リストのマージ、高速/低速ポインタ、ダミーノード、サイクル検出。問題文の下にあるパターンが見えれば、ゼロから解くのではなく、小さな道具箱から道具を選ぶだけになります。
これは誇張ではありません。主要なコーディングプラットフォームで頻出するリンクリスト問題を見直すと、この 5 カテゴリが出題の大半を占めることが分かります。LeetCode の厳選問題集 と NeetCode のロードマップ は、リンクリスト頻出順で絞ると、どちらも同じ問題群を浮かび上がらせます。
実際にはどう見えるか
各パターンは、代表的な問題に直接対応します。
- 反転 → Reverse Linked List (LeetCode 206)。上の反復的な 3 ポインタ手法がテンプレートです。
- マージ → Merge Two Sorted Lists (LeetCode 21)。2 本のポインタで両方のリストを走査し、先頭にダミーノードを置きます。
- 高速/低速ポインタ → Middle of the Linked List (LeetCode 876)、加えてサイクル検出 (LeetCode 141)。
- ダミーノード → Remove Nth Node From End (LeetCode 19)、Merge Two Sorted Lists。
- サイクル検出 → Linked List Cycle (LeetCode 141)、Linked List Cycle II (LeetCode 142)。
新しい問題が目の前に来たとき、最初に考えるべきは「どう解くか?」ではありません。「この 5 つのうち、どのパターンに見えるか?」です。この捉え直しだけで、真っ白なエディタを見つめる時間をかなり減らせます。
パターン認識が暗記より強い理由
多くの企業の面接官は、特定の解法を暗記しているかどうかを見ているわけではありません。問題の構造を素早く見抜き、正しい判断を始められるかを見ています。「長さを知らなくても末尾からの位置を求めたいので、これは高速/低速ポインタの問題に見えます」と言える候補者のほうが、黙って正しいコードを出す候補者より、準備ができているように見えます。そこで示されるのが、パターン認識です。
先頭が特別扱いになるなら、ダミーノードを使って時間を節約する
要するに、head を特別な存在として扱わないためです
ダミーノードの目的は一つです。リストの先頭は、驚くほど多くの問題で特別ケースになります。`if head is None`、`if head を削除している`、`if 最初のノードがマージ先` といった明示的な分岐で処理すると、核心ロジックとは関係のない複雑さが増えます。
ダミーノードは、`next` ポインタが `head` を指す `ListNode(0)` の使い捨てノードです。すると、アルゴリズムは最初の実ノードを他のノードと区別する必要がなくなります。常にその前にノードがあるからです。
実際にはどう見えるか
ダミーノードなしで 2 つのソート済みリストをマージするには、どちらのリストが初期 head を提供するかを決めるための別チェックが必要です。ダミーノードを使うとこうなります。
最後の `dummy.next` が、マージ後リストの本当の先頭です。ダミーがなければ、ループの前に結果の先頭ノードを決める条件分岐が必要になります。ダミーがあれば、ループはすべてのケースを同じように処理できます。実際の解答では、これによって 3 つの個別のエッジケース判定をコードから消せました。安全そうに見えて、実際には解答がきれいではないことを示してしまう類いの判定です。
高速/低速ポインタは、中間ノード問題以上のものを解く
同じ手法で、中間、サイクル、末尾から n 番目の削除ができる
高速/低速ポインタが機能するのは、同じリスト上を速度の違う 2 本のポインタが進むことで、予測可能な距離関係が生まれるからです。`fast` を `slow` の 2 倍の速度で進めれば、`fast` が終端に着いたとき `slow` は中央にいます。サイクルの中で両方を進めれば、やがて一致します。`fast` を `slow` より n ステップ先に置いておけば、`fast` が `None` になったとき `slow` は末尾から n ノード目にいます。
これは一つの構造的な洞察で、3 つの直接的な応用があります。基礎となる数学は毎回同じです。
実際にはどう見えるか
中間ノード:
サイクル検出（Floyd のアルゴリズム）:
末尾から n 番目の削除: `fast` を `slow` より n+1 ステップ先に置きます（どちらもダミーノードから開始）。その後、両方を 1 ステップずつ進めます。`fast` が `None` になったとき、`slow.next` が削除対象ノードです。
ループ条件 `while fast and fast.next` は、この 3 つすべてで同じです。そこが重要です。一度書けば、毎回同じように書けるようになります。
候補者がこのパターンを複雑にしすぎる理由
最もよくあるミスは、ポインタ間の距離を一歩ずつ追うのではなく、記憶から解法を復元しようとすることです。サイクル検出のコードを暗記していても、なぜポインタが出会うのかを内面化していない候補者は、面接官に「サイクルが 3 番目のノードから始まる場合はどうなりますか?」と聞かれた瞬間に固まります。5 ノードの例を紙に書き、各ステップで各ポインタがどこにいるかをラベル付けしてみてください。するとパターンはすぐに見え、プレッシャー下でも見え続けます。
CLRS（Introduction to Algorithms） によれば、Floyd のサイクル検出の正しさは、ループ内の 2 本のポインタに対する剰余算の性質から直接導かれます。それを理解すると、このアルゴリズムは恣意的なものではなく、覚えやすいものになります。
ランダムな問題をこなすのではなく、適切な練習問題を選ぶ
まずは小さな成功から始め、次に実際にパターンを組み合わせる問題へ進む
ランダムに問題をこなしても、結果もランダムになります。構造化された練習の階段は、再利用可能なパターン認識を育てます。リンクリスト面接の準備をするジュニア候補者にとっては、量より順序のほうが重要です。
まずは走査と基本操作から始めます。反復でリストを反転し、次に再帰で反転します。その後、2 つ目のパターンを導入する問題へ進みます。ソート済み 2 リストのマージ（マージ + ダミーノード）、中間ノードの検索（高速/低速）、サイクル検出（等価比較を伴う高速/低速）です。これらが自動化されたら、2 つのパターンを組み合わせる問題へ進みます。末尾から n 番目の削除（ダミーノード + 高速/低速のギャップ）、リンクリストの回文（高速/低速で中央を見つけてから後半を反転）、リオーダー（中央 + 反転 + マージ）です。
この組み合わせ段階を終えてから、Reverse Nodes in k-Group や LRU Cache に取り組むべきです。これらの問題は、より簡単なパターンを完全に内面化していることを前提にしています。
実際にはどう見えるか
ジュニア候補者向けの、順序を意識したコンパクトな学習階段は次の通りです。
- Reverse Linked List (LeetCode 206) — 反復と再帰
- Merge Two Sorted Lists (LeetCode 21) — ダミーノードの基本
- Middle of the Linked List (LeetCode 876) — 高速/低速の基本
- Linked List Cycle (LeetCode 141) — サイクル検出
- Remove Nth Node From End (LeetCode 19) — ダミーノード + ポインタギャップ
- Palindrome Linked List (LeetCode 234) — 中間 + 反転の組み合わせ
- Reorder List (LeetCode 143) — 中間 + 反転 + マージを一度に行う
この順番で 7 問、それぞれがどのパターンを教えているのかを意識しながら取り組みます。ランダムな順で 30 問解くより、はるかに有益な 1 週間の準備になります。NeetCode の blind 75 ロードマップ も、まさにこの理由で似た順序に並べています。
良い解法を壊す Python 特有のミスを避ける
参照を失うことは、最も小さくて高くつくミスです
Python のリンクリスト問題は、ほかの何よりも一つのミスを厳しく罰します。それは、何を指していたかを保存する前にポインタを再代入することです。リストはエラーを出しません。ただ静かに切れて、出力は間違います。しかも、ポインタの状態を声に出していなければ、追跡も難しいのです。
ルールは機械的です。`current.next` を変える前に、それを変数へ保存すること。`current` を動かす前に、どこへ行くかを保存すること。これは防御的コーディングではなく、ポインタ操作における正しい実行順序です。
None チェックは飾りではありません
空リスト (`head is None`) と 1 ノードのリスト (`head.next is None`) は、最も多くの解法を壊す 2 つのエッジケースです。少なくとも 2 ノードあることを前提にした走査ループは、1 ノード入力で `AttributeError` を起こします。対象ノードが head ではないと仮定した削除は、壊れたリストを返します。コードを書く前にこれらのケースを口に出すだけで、問題をきちんと考えていることが面接官に伝わります。これは細かさではなく、面接の技術です。
実際にはどう見えるか
壊れた削除と修正版を示します。
ダミーノードによって、head 削除のエッジケースがなくなります。削除後に早期 return することで、2 回進めてしまう問題を防げます。これは賢い小技ではありません。面接で最初に試される入力で Python のリンクリスト解答が壊れないようにする標準的なパターンです。
Verve AI で Python のリンクリスト面接を突破する方法
このガイドが示してきた構造上の問題、つまりパターンは分かっているのに、ライブで説明しようとすると筋道を見失ってしまう問題は、読むだけでは解決しません。実際の圧力に近い状況で声に出して繰り返し、説明が自動化されるまでやることで初めて解決します。
Verve AI Coding Copilot は、まさにそのギャップのために作られています。LeetCode、HackerRank、CodeSignal で問題を解いている最中に画面を読み取り、一般的なプロンプトではなく、実際に書いているコードに反応します。ポインタロジックがずれたり、エッジケース処理が不十分だったりすると、Verve AI Coding Copilot は定型文ではなく、文脈に沿った具体的な問題点を示します。Secondary Copilot 機能は、つまずいてポインタ状態を一つずつ考え直したいときでも、現在の位置を見失わずに 1 問に集中するのを助けます。そして、ライブの技術面接中は見えないまま なので、面接が始まった瞬間にサポートが止まることもありません。このガイドの練習階段を進む候補者にとって、Verve AI Coding Copilot は一人での反復練習をコーチ付きの繰り返しに近づけます。パターン認識が実際に身につくのは、まさにその形です。
FAQ
Q: Python におけるリンクリストとは何ですか? 面接上、配列とどう違うのですか?
リンクリストは、各ノードが値と次のノードへの参照を持つノード列です。配列とは異なり、連続したメモリブロックもインデックスベースのアクセスもありません。先頭からポインタをたどって移動します。面接上の重要な違いは時間計算量です。配列は O(1) のランダムアクセスを提供しますが、途中挿入・削除は O(n) です。リンクリストは、ポインタさえあれば挿入・削除が O(1) ですが、位置を探すための走査は O(n) です。
Q: 面接でよく試されるリンクリストの基本パターンは何ですか?
出題の大半をカバーする 5 つのパターンは、反転（反復の 3 ポインタ）、ソート済み 2 リストのマージ（2 ポインタ + ダミーノード）、高速/低速ポインタ（中央、サイクル、末尾から n 番目）、ダミーノード（head のエッジケースをなくす）、サイクル検出（Floyd のアルゴリズム）です。多くの問題は、この 5 つの仕組みの見え方を変えただけのものです。
Q: 基本的な ListNode クラスの書き方と、Python での走査・挿入・削除・反転のやり方は?
最小構成のクラスは `class ListNode: def __init__(self, val=0, next=None)` です。走査は `current = head; while current: current = current.next` です。削除では、付け替える前に `current.next` を保存します。反転では `prev`、`current`、`next_node` の 3 ポインタを使い、参照を失わない順序で進めます。3 節の反復反転パターンが、その正確な手順を示しています。
Q: ダミーノードはいつ使うべきで、head 削除やマージをどう簡単にしますか?
リストの head が変わる、あるいは消える可能性があるなら、ダミーノードを使います。たとえば head 削除、マージ、末尾から n 番目の削除です。ダミーは実際の head の前に置かれるので、アルゴリズムはすべてのノードを同じように扱えます。最終的には、どのノードが新しい head になったかを追跡する代わりに `dummy.next` を返します。最初のノードに対する条件分岐を取り除きつつ、論理的な複雑さは増やしません。
Q: 高速/低速ポインタで、中間ノード・サイクル検出・末尾から n 番目の削除をどう解きますか?
中間ノードでは、`fast` または `fast.next` が `None` になるまで `slow` を 1 ステップ、`fast` を 2 ステップ進めます。すると `slow` が中央にいます。サイクル検出では同じ動きで、途中で `slow == fast` になればサイクルがあります。末尾から n 番目の削除では、`fast` を `slow` より n+1 ステップ先（両方ともダミーノードから開始）に置き、その後は両方を 1 ステップずつ進めます。`fast` が `None` になったとき、`slow.next` が対象ノードです。
Q: リンクリストの面接回答で、必ず触れるべきエッジケースは何ですか?
必ず触れるべきなのは、空リスト (`head is None`)、1 ノードのリスト、2 ノードのリスト（特に反転とマージ）、そして対象ノードが head である場合です。コードを書く前にこれらを挙げることで、問題をきちんと考えていることが伝わります。これらを見落として、面接官にその入力で失敗するケースを見つけられるのは、正しい解答が点を落とす最も一般的なパターンです。
Q: ジュニア候補者が自信をつけるために、最初に練習すべきリンクリスト問題はどれですか?
順番は、Reverse Linked List、Merge Two Sorted Lists、Middle of the Linked List、Linked List Cycle、Remove Nth Node From End、Palindrome Linked List、Reorder List です。この順序の各問題が、特定のパターンまたはパターンの組み合わせを教えてくれます。順に解くことで、複数技法を組み合わせる問題に入る前の基盤ができます。
Q: リンクリストのトレードオフとポインタ操作を、面接官に分かりやすく説明するには?
まずメモリモデルから話します。配列は連続メモリを使うので O(1) アクセスができ、リンクリストは散らばったノードを使うので、既知の位置への挿入・削除が O(1) です。そのうえで、実用上の制限も率直に述べます。走査は O(n) であり、Python では多くの本番用途に `deque` のほうが適しています。ポインタ操作については、各ステップでポインタ状態を声に出して説明します。「`current.next` を付け替える前に `next` を保存しています」という具合です。その説明こそが、仕組みを理解している候補者と、コードを暗記しただけの候補者を分けます。
---
リンクリストの百科事典が必要だったわけではありません。必要だったのは、最初のノード構築から最後のエッジケースまでポインタを正しく保てる、Python ファーストの実戦的な手引きです。このガイドで扱ったパターン — 反転、マージ、高速/低速、ダミーノード、サイクル検出 — は、主要な面接プラットフォームのあらゆるバリエーション、あらゆるレベルで現れるものと同じです。練習階段を順番に進み、毎回ポインタ状態を声に出し、解答コードを 1 行でも書く前にエッジケースを確認してください。リンクリスト面接での自信は、あり得るすべての問題を見たことからは生まれません。少数の仕組みを十分に内面化し、新しい問題が読み終わる前に見覚えのあるものだと感じられることから生まれます。
Drew Sullivan
アーカイブ