【要約】Reorder Linked List [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
学習者が単方向連結リストの並べ替え問題に取り組む際、配列のような末尾からのインデックスアクセスができない制約に直面する。筆者は当初、以下の課題に陥っていた。
- ・単方向連結リストは後ろ方向への走査が不可能である。
- ・全ノードを一時的な配列に保存する方法は、空間計算量O(n)を要する。
- ・既存のアルゴリズムを組み合わせるという発想が欠如していた。
// Approach
開発者は、新しいアルゴリズムを考案するのではなく、既知のテクニックを3つのステップに分解して組み合わせる手法を採用した。
- ・Fast/Slowポインタ（ウサギと亀）を用いて、リストの中間地点を特定する。
- ・中間地点以降のリストを、ポインタの付け替えにより反転させる。
- ・前半部分と反転した後半部分のノードを、一時変数を用いて交互に結合する。
// Result
空間計算量をO(1)に抑えた、in-placeな並べ替えを実現した。これにより以下の成果を得ている。
- ・追加のメモリ消費を最小限に抑えた効率的な実装を実現した。
- ・「中間特定」「反転」「結合」という部品の組み合わせによる、論理的な問題分解を習得した。
- ・ポインタ操作における一時変数（tmp）の真の役割を明確化した。
Senior Engineer Insight
> 本件は、単一のアルゴリズムを覚えるのではなく、既存の「部品」をいかに組み合わせるかという、エンジニアリングの本質を示している。大規模システムにおいて、メモリ制約が厳しい環境ではO(1)の空間計算量は極めて重要だ。ポインタ操作はバグを誘発しやすいが、適切に分解・管理できれば、極めて効率的な実装が可能となる。部品化された思考こそが、複雑な実装を制御する鍵である。