C++でのリンクリストの逆順化方法

リンクリストのノードを逆順にリンクする方法:

#include <iostream>
struct Node {
    int data;
    Node* next;
};
// リンクリストを逆順にする関数
Node* reverseLinkedList(Node* head) {
    Node* current = head;
    Node* prev = nullptr;
    Node* next = nullptr;
    while (current != nullptr) {
        next = current->next; // 次のノードを保存
        current->next = prev; // currentのnextを前のノードに設定
        prev = current; // prevをcurrentに更新
        current = next; // currentを次のノードに進める
    }
    return prev; // 新しいヘッドノードを返す
}
// 逆順になったリンクリストを表示する関数
void printLinkedList(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}
int main() {
    // リンクリストの作成
    Node* head = new Node{1, nullptr};
    Node* second = new Node{2, nullptr};
    Node* third = new Node{3, nullptr};
    head->next = second;
    second->next = third;
    std::cout << "元のリンクリスト: ";
    printLinkedList(head);
    // リンクリストを逆順にする
    Node* reversedHead = reverseLinkedList(head);
    std::cout << "逆順化されたリンクリスト: ";
    printLinkedList(reversedHead);
    // メモリの解放
    delete head;
    delete second;
    delete third;
    return 0;
}

この方法では、ノードのリンクを逆にすることでリンクリストを逆順にします。ノードの順番を逆にするだけであり、データの値は変更されません。

リンクリストを配列に変換し、配列を逆順にする方法:

#include <iostream>
#include <vector>
struct Node {
    int data;
    Node* next;
};
// リンクリストを逆順にする関数
Node* reverseLinkedList(Node* head) {
    std::vector<int> values;
    Node* current = head;
    while (current != nullptr) {
        values.push_back(current->data);
        current = current->next;
    }
    current = head;
    int index = values.size() - 1;
    while (current != nullptr) {
        current->data = values[index];
        current = current->next;
        index--;
    }
    return head;
}
// 逆順になったリンクリストを表示する関数
void printLinkedList(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}
int main() {
    // リンクリストの作成
    Node* head = new Node{1, nullptr};
    Node* second = new Node{2, nullptr};
    Node* third = new Node{3, nullptr};
    head->next = second;
    second->next = third;
    std::cout << "元のリンクリスト: ";
    printLinkedList(head);
    // リンクリストを逆順にする
    Node* reversedHead = reverseLinkedList(head);
    std::cout << "逆順化されたリンクリスト: ";
   printLinkedList(reversedHead);
    // メモリの解放
    delete head;
    delete second;
    delete third;
    return 0;
}

この方法では、リンクリストの要素を配列に変換し、配列を逆順にすることでリンクリストを逆順にします。最後に、逆順になった値をリンクリストに戻しています。

これらはリンクリストを逆順にするためのいくつかの一般的な方法です。他にも様々なアプローチがありますが、ここで紹介した方法は比較的シンプルで理解しやすいものです。お好みや要件に合わせて、最適な方法を選択してください。