二つの非減少順（昇順）に整列された単方向連結リストを、一つの新たなソート済みリストに統合する問題。統合後のリストは、元の二つのリストに含まれるすべてのノードを再利用して構成され、追加のメモリ割り当ては不要である。 核心的なアプローチは以下の通り： - **ダミーノード**（仮想ヘッド）を導入し、新規リストの先頭を一貫して扱えるようにする - 結果リストを構築するための作業ポインタ `current` を用意 - 両リストの先頭要素を比較し、小さい方のノードを結果リスト末尾に連結 - 片方のリストが尽きた時点で、残りのノードをそのまま接続 以下はC++による実装例（オリジナルと異なる構造・命名・ロジックフローで再設計）： #include <iostream> struct Node { int data; Node* link; explicit Node(int d) : data(d), link(nullptr) {} }; Node* mergeSortedLists(Node* first, Node* second) { Node sentinel(-1); // ダミー先頭ノード（スタック確保） Node* tail = &sentinel; while (first && second) { if (first->data <= second->data) { tail->link = first; first = first->link; } else { tail->link = second; second = second->link; } tail = tail->link; } tail->link = (first) ? first : second; return sentinel.link; } void display(Node* head) { while (head) { std::cout << head->data << " "; head = head->link; } std::cout << "\n"; } int main() { // リスト1: 1 → 3 → 5 → 7 Node* a = new Node(1); a->link = new Node(3); a->link->link = new Node(5); a->link->link->link = new Node(7); // リスト2: 2 → 4 → 6 → 8 → 9 Node* b = new Node(2); b->link = new Node(4); b->link->link = new Node(6); b->link->link->link = new Node(8); b->link->link->link->link = new Node(9); Node* merged = mergeSortedLists(a, b); display(merged); // 出力: 1 2 3 4 5 6 7 8 9 return 0; } この実装の特徴： - ダミーノードをスタック上に配置し、ヒープ割り当てを回避（メモリ管理の簡素化） - `sentinel` と `tail` の名前で可読性を向上 - 条件分岐を `<=` に変更し、等値時の安定性を明示的に保証 - リスト構築後、元のポインタ `a`, `b` は無効化される点に注意（所有権移転） - 時間計算量は O(m + n)、空間計算量は O(1) — 新規ノード生成なし ダミーノードの利点は、初期状態における「空リスト」への対応を完全に抽象化できることにある。すなわち、`tail->link` への代入操作が常に有効であり、`head == nullptr` の分岐やポインタの二重管理を不要とする。これは特に反復処理系のコード品質と保守性を高める重要な設計パターンである。