連結リストを反転するCプログラムの解説【反復法・再帰法の2通り】

この記事では、連結リスト（Linked List）が与えられたときに、それを反転するプログラムの作成方法を解説します。

作成するプログラムは、与えられた連結リストのリンクの向きを逆にし、反転後の連結リストを返します。

連結リストとは

連結リストとは、データ項目を格納するノードがリンクで順につながったデータ構造です。各ノードには、次のノードへの接続（ポインタ）が含まれています。

連結リストの反転とは

「連結リストの反転」とは、リスト内のリンクの向きをすべて逆向きにして、新しい連結リストを作る操作のことです。反転後は、元のリストの先頭ノードが末尾ノードになり、元の末尾ノードが新しい先頭（head）ノードになります。

例

9 -> 32 -> 65 -> 10 -> 85 -> NULL

上記の連結リストを反転すると、次のようになります。

85 -> 10 -> 65 -> 32 -> 9 -> NULL

反転のアルゴリズム

連結リストを反転するには、previous（前）・current（現在）・after（次）という3つの補助ポインタを使用します。

1. previous と after を NULL で初期化し、current をリストの先頭ノードに設定します。
2. current が NULL になるまで、以下の処理を繰り返します。

after = current->next;
current->next = previous;
previous = current;
current = after;

ループが終了した時点で、previous が指しているノードが反転後のリストの先頭になります。

実装方法は大きく分けて2つあります。1つは反復法（イテレーティブ）、もう1つは再帰法です。それぞれのプログラムを見ていきましょう。

プログラム1：末尾再帰による連結リストの反転

#include <stdio.h>
struct Node {
    int data;
    struct Node* next;
};
Node* insertNode(int key) {
    Node* temp = new Node;
    temp->data = key;
    temp->next = NULL;
    return temp;
}
void tailRecRevese(Node* current, Node* previous, Node** head){
    if (!current->next) {
        *head = current;
        current->next = previous;
        return;
    }
    Node* next = current->next;
    current->next = previous;
    tailRecRevese(next, current, head);
}
void tailRecReveseLL(Node** head){
    if (!head)
        return;
    tailRecRevese(*head, NULL, head);
}
void printLinkedList(Node* head){
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}
int main(){
    Node* head1 = insertNode(9);
    head1->next = insertNode(32);
    head1->next->next = insertNode(65);
    head1->next->next->next = insertNode(10);
    head1->next->next->next->next = insertNode(85);
    printf("Linked list : \t");
    printLinkedList(head1);
    tailRecReveseLL(&head1);
    printf("Reversed linked list : \t");
    printLinkedList(head1);
    return 0;
}

出力

Linked list : 9 32 65 10 85
Reversed linked list : 85 10 65 32 9

このプログラムでは、tailRecRevese 関数が自分自身を呼び出す末尾再帰の形でリンクを逆方向につなぎ替えています。最後のノードに到達した時点で、そのノードを新しい head として設定します。

プログラム2：反復法による連結リストの反転

#include <stdio.h>
struct Node {
    int data;
    struct Node* next;
    Node(int data){
        this->data = data;
        next = NULL;
    }
};
struct LinkedList {
    Node* head;
    LinkedList(){
        head = NULL;
    }
    void interReverseLL(){
        Node* current = head;
        Node *prev = NULL, *after = NULL;
        while (current != NULL) {
            after = current->next;
            current->next = prev;
            prev = current;
            current = after;
        }
        head = prev;
    }
    void print() {
        struct Node* temp = head;
        while (temp != NULL) {
            printf("%d ", temp-> data);
            temp = temp->next;
        }
        printf("\n");
    }
    void push(int data){
        Node* temp = new Node(data);
        temp->next = head;
        head = temp;
    }
};
int main() {
    LinkedList linkedlist;
    linkedlist.push(85);
    linkedlist.push(10);
    linkedlist.push(65);
    linkedlist.push(32);
    linkedlist.push(9);
    printf("Linked List : \t");
    linkedlist.print();
    linkedlist.interReverseLL();
    printf("Reverse Linked List : \t");
    linkedlist.print();
    return 0;
}

出力

Linked List : 9 32 65 10 85
Reverse Linked List : 85 10 65 32 9

こちらのプログラムでは、push メソッドがリストの先頭に要素を追加していくため、挿入順とは逆の「9 32 65 10 85」の並びのリストが構築されます。その後、interReverseLL メソッドが前述の3ポインタを使った反復処理でリストを反転しています。

計算量について

• 時間計算量： どちらの手法でも、各ノードを一度ずつ処理するため O(n) です。
• 空間計算量： 反復法は補助ポインタ3個だけで済むため O(1)。一方、再帰法は呼び出しスタックをノード数分使用するため O(n) となります。

大きなリストを扱う場合やメモリ効率を重視する場合は、反復法を採用するのが一般的です。