C++で連結リストの先頭要素を末尾へ移動する方法を解説

はじめに

連結リスト（Linked List）が与えられたとき、先頭の要素を末尾へ移動する操作を行います。この操作は、ポインタの付け替えだけで実現できる連結リストの基本的なテクニックの一つです。まずは具体例を見てみましょう。

入力例

1 -> 2 -> 3 -> 4 -> 5 -> NULL

出力例

2 -> 3 -> 4 -> 5 -> 1 -> NULL

アルゴリズム

先頭ノードを末尾へ移動するには、以下の手順に従います。

• 連結リストを初期化します。

• 連結リストが空、またはノードが1つしかない場合は、何もせずに処理を終了します。

• 連結リストの末尾ノードを探します。

• 2番目のノードを新しいヘッド（先頭）として設定します。

• 元の先頭ノードと末尾ノードのリンクを更新します。

C++での実装

以下は、上記のアルゴリズムをC++で実装したサンプルコードです。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
void moveFirstNodeToEnd(struct Node** head) {
    if (*head == NULL || (*head)->next == NULL) {
        return;
    }
    struct Node* firstNode = *head;
    struct Node* lastNode = *head;
    while (lastNode->next != NULL) {
        lastNode = lastNode->next;
    }
    *head = firstNode->next;
    firstNode->next = NULL;
    lastNode->next = firstNode;
}
void addNewNode(struct Node** head, int new_data) {
    struct Node* newNode = new Node;
    newNode->data = new_data;
    newNode->next = *head;
    *head = newNode;
}
void printLinkedList(struct Node* node) {
    while (node != NULL) {
        cout << node->data << "->";
        node = node->next;
    }
    cout << "NULL" << endl;
}
int main() {
    struct Node* head = NULL;
    addNewNode(&head, 1);
    addNewNode(&head, 2);
    addNewNode(&head, 3);
    addNewNode(&head, 4);
    addNewNode(&head, 5);
    addNewNode(&head, 6);
    addNewNode(&head, 7);
    addNewNode(&head, 8);
    addNewNode(&head, 9);
    moveFirstNodeToEnd(&head);
    printLinkedList(head);
    return 0;
}

コードの解説

moveFirstNodeToEnd 関数では、まずリストが空または単一ノードの場合を除外しています。その後、lastNode ポインタでリストを走査して末尾ノードを見つけます。見つかったら、ヘッドを2番目のノードに更新し、元の先頭ノードの next を NULL に、末尾ノードの next を元の先頭ノードに向けることで、先頭要素を末尾へ移動させています。

出力

上記のコードを実行すると、以下の結果が得られます。

8->7->6->5->4->3->2->1->9->NULL

なお、このサンプルコードでは addNewNode 関数が新しいノードを常に先頭に挿入するため、リストは挿入順とは逆の順序（9→8→…→1）で構築されています。その結果、先頭にあった「9」が末尾へ移動した出力になります。

計算量

• 時間計算量： 末尾ノードを探すためにリストを一度走査するため、O(n) となります（n はノード数）。

• 空間計算量： 追加で必要なメモリはポインタ数個分のみで、O(1) です。

まとめ

連結リストの先頭要素を末尾へ移動する操作は、ポインタの付け替えだけで効率的に実現できます。配列と異なり要素のシフトが不要な点が連結リストの大きな利点です。このテクニックは、リストの回転操作など、さまざまな応用問題の基礎にもなります。