C++で連結リストを挿入ソートする方法【実装例つき】

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

アルゴリズムの手順

この問題は、次の手順に従って解くことができます。

• 任意の値を持つダミーノード（dummy）を新しく作成します
• node を与えられたリストの先頭として設定します
• node が NULL でない間、以下を繰り返します
  • newNode = node の次のノード、dummyHead = dummy の次のノード、prevDummyHead = dummy とします
  • 無限ループの中で次の判定を行います
    • dummyHead が存在しない、または dummyHead の値が node の値より大きい場合
      • node の next を dummyHead に設定します
      • prevDummyHead の next を node に設定します
      • ループを抜けます
    • それ以外の場合は、prevDummyHead = dummyHead、dummyHead = dummyHead の次のノード として探索位置を進めます
  • node = newNode として次のノードの処理へ移ります
• すべての処理が完了したら、dummy の次のノード（＝ソート済みリストの先頭）を返します

C++による実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class ListNode{
    public:
        int val;
        ListNode *next;
        ListNode(int data){
            val = data;
            next = NULL;
        }
};
ListNode *make_list(vector<int> v){
    ListNode *head = new ListNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        ListNode *ptr = head;
        while(ptr->next != NULL){
            ptr = ptr->next;
        }
        ptr->next = new ListNode(v[i]);
    }
    return head;
}
void print_list(ListNode *head){
    ListNode *ptr = head;
    cout << "[";
    while(ptr){
        cout << ptr->val << ", ";
        ptr = ptr->next;
    }
    cout << "]" << endl;
}
class Solution {
    public:
    ListNode* insertionSortList(ListNode* a) {
        ListNode* dummy = new ListNode(-1);
        ListNode* node = a;
        ListNode* nextNode;
        ListNode* dummyHead;
        ListNode* prevDummyHead;
        while(node != NULL){
            nextNode = node->next;
            dummyHead = dummy->next;
            prevDummyHead = dummy;
            while(1){
                if(!dummyHead || dummyHead->val > node->val){
                    node->next = dummyHead;
                    prevDummyHead->next = node;
                    break;
                }
                prevDummyHead = dummyHead;
                dummyHead = dummyHead->next;
            }
            node = nextNode;
        }
        return dummy->next;
    }
};
main(){
    vector<int> v = {5,3,2,0,-4,7};
    ListNode *head = make_list(v);
    Solution ob;
    print_list(ob.insertionSortList(head));
}

入力

{5,3,2,0,-4,7}

出力

[-4, 0, 2, 3, 5, 7]

計算量とポイント

このアルゴリズムの時間計算量は、最悪ケースおよび平均ケースで O(n²) です。一方、すでにほぼ整列されたリストに対しては比較回数が減るため高速に動作します。また、必要な追加メモリは定数（O(1)）のみであり、配列のように要素をシフトする必要がなくポインタの付け替えだけで挿入できるため、連結リストは挿入ソートと特に相性の良いデータ構造といえます。

ダミーノードを使用することで、先頭への挿入時に特別な分岐処理を書く必要がなくなり、実装がシンプルになる点も重要なポイントです。