C++で連結リストを挿入ソートする方法を解説

連結リストが与えられたとき、そのリストに対して挿入ソート（Insertion Sort）を実行することを考えてみましょう。例えば、リストが [9,45,23,71,80,55] の場合、ソート後のリストは [9,23,45,55,71,80] となります。

配列と異なり、連結リストでは要素の挿入・削除がポインタの付け替えだけで行えるため、挿入ソートとの相性が良いという特徴があります。

アルゴリズムの手順

この問題を解くために、以下の手順に従います。

• 任意の値を持つダミーノード（番兵ノード）を新しく作成します。
• node を与えられたリストの先頭に設定します。
• node が NULL でない間、以下を繰り返します。
  • nextNode を node の次のノードとし、dummyHead をダミーの次のノード、prevDummyHead をダミー自身に設定します。
  • 以下の条件を満たすまでループします。
    • dummyHead が存在しない、または dummyHead の値が node の値より大きい場合：
      • node の次を dummyHead につなぎます。
      • prevDummyHead の次を node につなぎます。
      • ループを抜けます。
    • それ以外の場合は、prevDummyHead を dummyHead に、dummyHead をその次のノードに進めます。
  • node を nextNode に進めます。
• 最後に、ダミーの次のノード（ソート済みリストの先頭）を返します。

ダミーノードを用意することで、先頭への挿入処理を特別扱いせずに統一的なコードで書けるのがポイントです。

実装例

以下のC++コードで、実際の動作を確認してみましょう。

class Solution {
public:
    ListNode* insertionSortList(ListNode* a) {
        ListNode* dummy = new ListNode(-1);
        ListNode* node = a;
        while (node != NULL) {
            ListNode* nextNode = node->next;
            ListNode* dummyHead = dummy->next;
            ListNode* prevDummyHead = dummy;
            while (true) {
                if (!dummyHead || dummyHead->val > node->val) {
                    node->next = dummyHead;
                    prevDummyHead->next = node;
                    break;
                }
                prevDummyHead = dummyHead;
                dummyHead = dummyHead->next;
            }
            node = nextNode;
        }
        return dummy->next;
    }
};

入力

[9,45,23,71,80,55]

出力

[9,23,45,55,71,80]

計算量について

このアルゴリズムの時間計算量は O(n²) です。各ノードについて、ソート済み部分リストの中から挿入位置を線形探索するためです。一方、追加のメモリはダミーノードと数個のポインタのみで済むため、空間計算量は O(1) となります。要素数が少ないリストや、ほぼソート済みのデータに対しては効率的に動作します。