【C言語】リスト構造をマージソートする方法を解説

#include <stdio.h>
#include <stdlib.h>
// リストのノードを表す構造体
typedef struct Node {
    int data;
    struct Node* next;
} Node;
// リストを表示する関数
void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}
// リストを分割する関数
void splitList(Node* source, Node** front, Node** back) {
    Node* slow = source;
    Node* fast = source->next;
    // fastポインタを2つ進め、slowポインタを1つ進める
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    // slowポインタの次のノードを分割点として設定し、リストを分割する
    *front = source;
    *back = slow->next;
    slow->next = NULL;
}
// 2つのリストをマージする関数
Node* mergeLists(Node* a, Node* b) {
    Node* result = NULL;
    // ベースケース: どちらかのリストが空の場合、もう片方のリストを返す
    if (a == NULL) {
        return b;
    } else if (b == NULL) {
        return a;
    }
    // 2つのリストの先頭要素を比較し、小さい方をresultに追加する
    if (a->data <= b->data) {
        result = a;
        result->next = mergeLists(a->next, b);
    } else {
        result = b;
        result->next = mergeLists(a, b->next);
    }
    return result;
}
// リストをマージソートする関数
void mergeSort(Node** head) {
    Node* current = *head;
    Node* a;
    Node* b;
    // ベースケース: リストが空または要素が1つの場合、ソート済みとみなす
    if (current == NULL || current->next == NULL) {
        return;
    }
    // リストを分割する
    splitList(current, &a, &b);
    // 分割したリストを再帰的にマージソートする
    mergeSort(&a);
    mergeSort(&b);
    // マージしたリストをheadに設定する
    *head = mergeLists(a, b);
}
int main() {
    // サンプルデータのリストを作成する
    Node* head = (Node*)malloc(sizeof(Node));
    Node* second = (Node*)malloc(sizeof(Node));
    Node* third = (Node*)malloc(sizeof(Node));
    Node* fourth = (Node*)malloc(sizeof(Node));
    head->data = 4;
    head->next = second;
    second->data = 2;
    second->next = third;
    third->data = 1;
    third->next = fourth;
    fourth->data = 3;
    fourth->next = NULL;
    printf("ソート前のリスト: ");
    printList(head);
    // リストをマージソートする
    mergeSort(&head);
    printf("ソート後のリスト: ");
    printList(head);
    // メモリの解放
    free(head);
    free(second);
    free(third);
    free(fourth);
    return 0;
}

ソート前のリスト: 4 2 1 3 
ソート後のリスト: 1 2 3 4