C言語でリストを反転させる方法は？

2年 ago
海斗, 葵
1 minute

C言語では、ポインタ操作によりリストを反転させることが可能である。

最初に、連結リストのノードを表す構造体を定義する必要があります。構造体には値（あらゆる型）を格納し、次のノードを指すポインタが含まれています。

struct Node {
    int data;
    struct Node* next;
};

次いで、リストを反転する関数を記述できる。その関数はリストの先頭ノードを引数として受け取り、ポインタ操作によりリストのノードの順序を並び替える。

struct Node* reverseList(struct Node* head) {
    struct Node* prev = NULL;
    struct Node* current = head;
    struct Node* next = NULL;
    
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    
    head = prev;
    
    return head;
}

この関数は3つのポインタを使用しています。prevは現在のノードの前のノードを格納するために使用され、currentは現在のノードを格納するために使用され、nextは現在のノードの次のノードを格納するために使用されます。ループでは、まずnextポインタを現在のノードの次のノードを指すようにします。次に、現在のノードのnextポインタを前のノードを指すようにします。次に、prevポインタを現在のノードを指し、currentポインタをnextノードを指すようにします。最後に、ヘッドノードを反転したリンクリストの最後のノードを指すようにします。

逆転連結リスト関数を使った例を示します。

int main() {
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    // 创建链表
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

    // 反转链表
    head = reverseList(head);

    // 打印反转后的链表
    struct Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }

    return 0;
}

出力は 3 2 1 になり、リストは反転に成功しました。

bannerAds