C++で双方向リンクリストを反転する2つのアプローチ

この記事では、双方向リンクリスト（doubly linked list）をC++で反転するための複数のアプローチを解説します。たとえば、次のような入力と出力を考えます。

入力 : {1, 2, 3, 4}
出力 : {4, 3, 2, 1}

真っ先に思いつく方法はおそらく1つだけですが、ここでは「通常のアプローチ」と「変則的なアプローチ」の2つの方法を紹介します。

通常のアプローチ（ポインタの入れ替え）

このアプローチでは、リストを先頭から順に走査しながら、各ノードのnextポインタとprevポインタを入れ替えていきます。走査が完了した時点で、リスト全体が反転された状態になります。

実装例

#include <bits/stdc++.h>

using namespace std;

class Node {
    public:
    int data;
    Node *next;
    Node *prev;
};

void reverse(Node **head_ref) {
    auto temp = (*head_ref) -> next;
    (*head_ref) -> next = (*head_ref) -> prev;
    (*head_ref) -> prev = temp;
    if(temp != NULL) {
        (*head_ref) = (*head_ref) -> prev;
        reverse(head_ref);
    }
    else
        return;
}
void push(Node** head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;

    new_node->prev = NULL;

    new_node->next = (*head_ref);
    if((*head_ref) != NULL)
        (*head_ref) -> prev = new_node ;

    (*head_ref) = new_node;
}
int main() {
    Node* head = NULL;
    push(&head, 6);
    push(&head, 4);
    push(&head, 8);
    push(&head, 9);
    auto node = head;
    cout << "Before\n" ;
    while(node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << "\n";
    reverse(&head);
    node = head;
    cout << "After\n";
    while(node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    return 0;
}

出力結果

Before
9 8 4 6
After
6 4 8 9

このアプローチの時間計算量はO(N)です。Nはリストのサイズを表します。線形時間で処理できるため、制約が大きい問題でも十分に対応できる優れた手法です。

変則的なアプローチ（スタックを利用）

名前からもわかるとおり、あまり一般的には思いつかない方法ですが、こちらも掘り下げてみましょう。このアプローチでは、まずスタックを用意し、リストを走査しながらノードへのポインタをすべてプッシュしていきます。その後、スタックからポップしながら各ノードのnextとprevを入れ替えることで、リストを反転させます。

実装例

#include <bits/stdc++.h>

using namespace std;

class Node {
    public:
    int data;
    Node *next;
    Node *prev;
};
void push(Node** head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;

    new_node->prev = NULL;

    new_node->next = (*head_ref);
    if((*head_ref) != NULL)
        (*head_ref) -> prev = new_node ;

    (*head_ref) = new_node;
}
int main() {
    Node* head = NULL;
    push(&head, 6);
    push(&head, 4);
    push(&head, 8);
    push(&head, 9);
    auto node = head;
    cout << "Before\n" ;
    while(node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << "\n";
    stack<Node*> s;
    node = head;
    while(node) {
        head = node;
        s.push(node);
        node = node -> next;
    }
    while(!s.empty()) {
        auto x = s.top();
        auto temp = x -> prev;
        x -> prev = x -> next;
        x -> next = temp;
        s.pop();
    }
    node = head;
    cout << "After\n";
    while(node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    return 0;
}

出力結果

Before
9 8 4 6
After
6 4 8 9

コードの解説

このアプローチでは、リストを走査しながらノードをスタックに格納し、その後スタックから取り出しながら各ノードのポインタを入れ替えることで、リストを反転させています。このプログラムの時間計算量もO(N)であり、制約が大きいケースにも適用可能です。

まとめ

この記事では、双方向リンクリストを反転する問題を、スタックを使う方法と使わない方法の2通りで解決しました。どちらのアプローチも、NをリストのサイズとしたときにO(N)の時間計算量で実行できます。さらに、この問題に対するC++の実装と、通常・変則的の両アプローチによる解法の流れを学びました。同じロジックは、C、Java、Pythonなど他の言語でも同様に実装できます。この記事が皆さんのお役に立てば幸いです。