C++で連結リストがペアごとにソートされているか判定する方法

ペアごとのソート判定とは

n個の要素を持つ連結リストLが与えられたとき、そのリストが「ペアごとにソートされているか」を判定します。たとえば、リストが {8, 10, 18, 20, 5, 15} である場合、(8, 10)、(18, 20)、(5, 15) の各ペアがいずれも昇順に並んでいるため、このリストはペアごとにソートされていると判断できます。要素数が奇数の場合は、ペアをなさない最後の1要素が無視されます。

アルゴリズムの考え方

アプローチは非常にシンプルです。リストを先頭から順に走査し、隣接する2つの要素を1組のペアとして取り出して、それぞれのペアが昇順に並んでいるかを確認します。ソートされていないペアが1つでも見つかった時点でfalseを返し、すべてのペアが正しくソートされていればtrueを返します。

処理手順

1. 先頭ノードから走査を開始します。
2. 現在のノードと次のノードの値を比較します。
3. 現在の値が次の値より大きい場合、そのペアはソートされていないためfalseを返します。
4. 問題がなければ、2ノード分先へ移動して次のペアを確認します。
5. リストの終端に達したらtrueを返します。

C++による実装例

#include <iostream>
using namespace std;
class Node {
public:
    int data;
    Node* next;
};
// リストの末尾にノードを追加する
void append(Node** head, int key) {
    Node* new_node = new Node;
    new_node->data = key;
    new_node->next = NULL;
    if (*head == NULL) {
        *head = new_node;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = new_node;
}
// リストがペアごとにソートされているか判定する
bool isPairwiseSorted(Node* head) {
    Node* temp = head;
    while (temp != NULL && temp->next != NULL) {
        // ペアが昇順でない場合はfalseを返す
        if (temp->data > temp->next->data) {
            return false;
        }
        temp = temp->next->next;
    }
    return true;
}
int main() {
    Node* head = NULL;
    int arr[] = {8, 10, 18, 20, 5, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < n; i++) {
        append(&head, arr[i]);
    }
    if (isPairwiseSorted(head)) {
        cout << "This is pairwise sorted" << endl;
    } else {
        cout << "This is not pairwise sorted" << endl;
    }
    return 0;
}

実行結果

This is pairwise sorted

計算量

時間計算量はO(n)(nはリストの要素数)です。リストを一度だけ走査すればよいため、非常に効率的なアルゴリズムです。また、追加の作業用メモリを必要としないため、空間計算量はO(1)となります。