C++で連結リストの最後の要素を先頭に移動する方法

連結リストが与えられたとき、最後の要素を先頭（ヘッド）へ移動させる必要があります。まず、具体的な例を見てみましょう。

入力

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

出力

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

アルゴリズム

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

• 連結リストが空であるか、ノードが1つしかない場合は、そのまま処理を終了して返します。

• 連結リストの最後のノードと、後ろから2番目のノードを探します。

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

• 後ろから2番目のノードのリンク（nextポインタ）を更新します。

実装

以下は、上記のアルゴリズムをC++で実装したものです。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
// 最後のノードを先頭へ移動する関数
void moveLastNodeToFront(struct Node** head) {
    if (*head == NULL || (*head)->next == NULL) {
        return;
    }
    struct Node* secondLastNode = *head;
    struct Node* lastNode = *head;
    while (lastNode->next != NULL) {
        secondLastNode = lastNode;
        lastNode = lastNode->next;
    }
    secondLastNode->next = NULL;
    lastNode->next = *head;
    *head = lastNode;
}
// 新しいノードを先頭に追加する関数
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);
    moveLastNodeToFront(&head);
    printLinkedList(head);
    return 0;
}

出力

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

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

この出力について補足します。addNewNode関数は常にリストの先頭に新しいノードを挿入するため、挿入完了時点での初期リストは「9 -> 8 -> 7 -> ... -> 1」という順序になっています。そこで最後のノード「1」を先頭へ移動すると、「1 -> 9 -> 8 -> ... -> 2」という結果になります。

なお、このアルゴリズムはリストを一度だけ走査すればよいため、計算量は O(n) です（n は連結リストのノード数）。空のリストやノードが1つのみのリストに対しても安全に動作する点もポイントです。