C++でソート・回転済み連結リストの回転数を求める方法

問題概要

ある連結リストが与えられます。このリストは、最初に昇順にソートされ、その後 K 個のノード分だけ回転（ローテーション）されたものです。この記事の目的は、元のリストに対する回転数 K を求めることです。

たとえば、以下のような連結リストが入力として与えられたとします。

5 → 7 → 9 → 1 → 3

このリストは、元のソート済みリスト

1 → 3 → 5 → 7 → 9

を 2 ノード分だけ回転したものになっています。つまり、この場合の K は 2 です。

具体例で理解する

例 1

入力： リスト： 5 → 7 → 9 → 1 → 3

出力：

• 連結リストの要素： 5 7 9 1 3
• ソート・回転済み連結リストの回転数： 3

説明： 元のソート済みリストを 3 回回転すると、入力リストが得られます。

1 → 3 → 5 → 7 → 9 （元のリスト）
9 → 1 → 3 → 5 → 7 （回転 1）
7 → 9 → 1 → 3 → 5 （回転 2）
5 → 7 → 9 → 1 → 3 （回転 3）

例 2

入力： リスト： 17 → 25 → 62 → 99

出力：

• 連結リストの要素： 17 25 62 99
• ソート・回転済み連結リストの回転数： 4

説明： 4 回の回転で再び元のリストに戻るため（完全な一周）、回転数は 4 となります。

17 → 25 → 62 → 99 （元のリスト）
99 → 17 → 25 → 62 （回転 1）
62 → 99 → 17 → 25 （回転 2）
25 → 62 → 99 → 17 （回転 3）
17 → 25 → 62 → 99 （回転 4）

アルゴリズムの考え方

回転された連結リストには必ず「次のノードの値が前のノードの値より小さくなる」境界点が 1 つ存在します。もし入力リストが完全にソートされているなら、それは元のリストの完全な一周（全長ぶんの回転）を表します。

基本的な手順は次のとおりです。

1. 先頭ノード（head）から走査を開始します。
2. 現在のノードの値が head ノードの値以上である限り、カウントを 1 ずつ増やしながら走査を続けます。
3. 現在のノードの値が head ノードの値より小さくなった時点でループを終了します。
4. このときのカウントが、元のリストに対する回転数 K になります。

処理の流れの詳細

• 入力リストを作成し、要素を挿入します。
• 関数 insert_node(struct List_Node** head, int data) は、単方向連結リストの先頭に新しいノードを挿入します。
• 関数 print(struct List_Node* node) は、while ループを使って先頭から末尾まで連結リストの要素を出力します。
• 関数 rotations(struct List_Node* head) は、連結リストの先頭ポインタを受け取り、入力リストを得るために元のリストに行われた回転数を返します。
• カウント変数 count を 0 で初期化します。
• temp 変数に head ノードのデータを格納します。
• while ループで連結リストの末尾（head != NULL）まで走査します。
• 現在のノードの値が temp 以上の場合は count をインクリメントします。
• 現在のノードの値が head ノードの値（temp）未満になった場合はループを抜けます。
• 最後に count を結果として返します。

C++ 実装コード

#include <bits/stdc++.h>
using namespace std;
struct List_Node{
    int data;
    struct List_Node* next;
};
int rotations(struct List_Node* head){
    int count = 0;
    int temp = head->data;
    while (head != NULL){
        if (temp > head->data){
            break;
        }
        count++;
        head = head->next;
    }
    return count;
}
void insert_node(struct List_Node** head, int data){
    struct List_Node* new_node = new List_Node;
    new_node->data = data;
    new_node->next = (*head);
    (*head) = new_node;
}
void print(struct List_Node* node){
    while (node != NULL){
        cout<<node->data<<" ";
        node = node->next;
    }
}
int main(){
    struct List_Node* head = NULL;
    insert_node(&head, 2);
    insert_node(&head, 1);
    insert_node(&head, 18);
    insert_node(&head, 35);
    insert_node(&head, 28);
    cout<<"Elements in the linked list are: ";
    print(head);
    cout<<"\nCount of rotations in sorted and rotated linked list are: "<<rotations(head);
    return 0;
}

実行結果

上記のコードを実行すると、以下の出力が生成されます。

Elements in the linked list are: 28 35 18 1 2
Count of rotations in sorted and rotated linked list are: 2

まとめ

このアルゴリズムは、連結リストを先頭から一度だけ走査すればよいため、時間計算量は O(n)、空間計算量は O(1) という効率的な手法です。ソート済みリストが回転されると値が降順に切り替わる境界点が必ず現れるという性質を利用することで、シンプルに回転数を特定できます。データ構造の操作やアルゴリズムの学習において、非常に応用範囲の広いテクニックです。