C++で片方向リンクリストを循環リンクリストに変換する方法

このチュートリアルでは、C++を使用して片方向リンクリスト（単方向連結リスト）を循環リンクリストに変換するプログラムの実装方法について詳しく解説します。

循環リンクリストとは、リストの末尾ノードのnextポインタが先頭ノードを指すようにしたデータ構造です。通常のリンクリストでは末尾ノードのnextがNULLを指しますが、この接続を先頭ノードへつなぎ替えることで、リスト全体を一周できるリング状の構造を作ることができます。

変換の考え方（アルゴリズム）

片方向リンクリストを循環リンクリストに変換する手順は非常にシンプルで、次の2ステップで実現できます。

1. 先頭ノードからスタートし、nextがNULLとなるノード（＝リストの末尾ノード）まで走査する。
2. 見つけた末尾ノードのnextポインタに、先頭ノードへの参照を代入する。

これだけでリスト全体がリング状につながり、循環リンクリストとして扱えるようになります。計算量はリストの長さを n とすると O(n) です。

C++での実装例

#include <bits/stdc++.h>

// リンクリストのノード構造体
struct Node {
    int data;
    struct Node* next;
};

// 片方向リンクリストを
// 循環リンクリストに変換する関数
struct Node* circular(struct Node* head) {
    struct Node* start = head;
    while (head->next != NULL)
        head = head->next;
    // 末尾ノードの next に先頭ノードを代入し、
    // 循環構造を完成させる
    head->next = start;
    return start;
}

void push(struct Node** head, int data) {
    // 新しいノードの生成
    struct Node* newNode = (struct Node*)malloc
    (sizeof(struct Node));
    // 新しいノードにデータを格納
    newNode->data = data;
    newNode->next = (*head);
    (*head) = newNode;
}

// 循環リンクリストの要素を表示する関数
void print_list(struct Node* node) {
    struct Node* start = node;
    while (node->next != start) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("%d ", node->data);
}

int main() {
    struct Node* head = NULL;
    push(&head, 15);
    push(&head, 14);
    push(&head, 13);
    push(&head, 22);
    push(&head, 17);
    circular(head);
    printf("Display list: \n");
    print_list(head);
    return 0;
}

実行結果

Display list:
17 22 13 14 15

コードのポイント解説

• circular関数： 先頭ノードを受け取り、nextがNULLになるまでリストを辿って末尾ノードを特定します。その末尾ノードのnextに先頭ノード（start）を代入することで、循環構造を完成させています。
• push関数： mallocで新しいノードを動的に生成し、常にリストの先頭に挿入します。このため、表示結果は挿入した順序と逆の「17 → 22 → 13 → 14 → 15」となります。
• print_list関数： 循環リンクリストは終端がないため、そのまま辿ると無限ループに陥ります。そこで開始ノードの位置をstartとして記憶しておき、再び先頭に戻ったタイミングでループを抜けることで安全に全要素を表示しています。

まとめ

片方向リンクリストを循環リンクリストへ変換する処理は、「末尾ノードまで走査し、そのnextを先頭ノードに向ける」だけの簡単な操作で実現できます。ただし、循環構造を持つリストを扱う際は終端判定が使えなくなるため、表示や探索の際には必ず開始位置を記録してループを制御することが重要です。ジョセフス問題やラウンドロビン方式のタスク管理など、循環リンクリストが活躍する場面は多いため、ぜひ本記事の実装を参考にしてみてください。