C++で昇順ソート済み循環リンクリストへ値を挿入する方法

ここでは、昇順にソートされた循環リンクリストのノードが1つ与えられたとき、値 insertVal を適切な位置に挿入し、挿入後もソートされた状態を保つ関数を実装する方法を解説します。

問題の概要

引数として渡されるノードは、リスト内の任意の1ノードへの参照であり、必ずしも先頭ノードとは限りません。挿入に適した位置が複数存在する場合は、どこに挿入しても構いません。

また、以下のようなケースにも対応する必要があります。

• リストが空の場合：新しい単一ノードからなる循環リンクリストを作成し、そのノードへの参照を返す
• リストが空でない場合：元のノードをそのまま返す

例として、head = [3,4,1]、insertVal = 2 が与えられた場合、出力は [3,4,1,2] となります。

アルゴリズムの手順

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

1. head が null（空リスト）の場合：
   • val を持つ新しいノードを head とする
   • head->next = head と設定し、自己参照の循環リストを作る
2. それ以外の場合：
   • curr = head->next、prev = head と初期化する
   • temp として val を持つ新しいノードを生成し、フラグ done = false を用意する
   • 無限ループの中で以下を判定する：
     • 通常の挿入ケース：curr->val >= val かつ prev->val <= val のときは、prev と curr の間に temp を挿入し、done = true としてループを抜ける
     • 境界をまたぐケース：prev->val > curr->val（最大値と最小値の境目）のとき、prev->val <= val または val <= curr->val であれば同様に挿入してループを抜ける
     • curr == head となったら一周したのでループを抜ける
     • それ以外は prev = curr、curr = curr->next としてポインタを進める
   • ループ後も done == false の場合（全ノードが同一の値など）は、head の直前に temp を挿入する
3. head を返す

C++による実装例

以下の実装を見ると、より理解が深まります。

#include <bits/stdc++.h>
using namespace std;
class Node {
public:
    int val;
    Node* next;
    Node() {}
    Node(int _val) {
        val = _val;
        next = NULL;
    }
    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
class Solution {
public:
    Node* insert(Node* head, int val) {
        if(!head){
            head = new Node(val);
            head->next = head;
        }
        else{
            Node* curr = head->next;
            Node* prev = head;
            Node* temp = new Node(val);
            bool done = false;
            while(1){
                if (curr->val >= val && prev->val <= val) {
                    prev->next = temp;
                    temp->next = curr;
                    done = true;
                    break;
                }
                if (prev->val > curr->val) {
                    if (prev->val <= val || val <= curr->val) {
                        prev->next = temp;
                        temp->next = curr;
                        done = true;
                        break;
                    }
                }
                if (curr == head)
                    break;
                prev = curr;
                curr = curr->next;
            }
            if(!done){
                temp->next = head;
                prev->next = temp;
                head = temp;
            }
        }
        return head;
    }
};
main(){
    Solution ob;
    Node *head = new Node(3);
    head->next = new Node(4);
    head->next->next = new Node(1, head);
    ob.insert(head, 2);
    Node *temp = head;
    if (head != NULL){
        do{
            cout << temp->val << " ";
            temp = temp->next;
        }
        while (temp != head);
    }
}

入力例

node *head = new Node(3);
head->next = new Node(4);
head->next->next = new Node(1, head);
insertVal = 2

出力結果

3 4 1 2

まとめ

このアルゴリズムでは、リストを一周しながら「挿入値が前後ノードの間に収まる位置」または「最大値と最小値の境界をまたぐ位置」を探索します。計算量はノード数を N とすると O(N)、必要な追加メモリは新ノード1つ分のみで O(1) です。空リストや全ノードが同値といったエッジケースも正しく処理できる点がポイントです。