[C 语言笔记--Day18] 用 linked list 实作 merge sort

题目来源

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next, *prev;
};

void display(struct node *start) {
    struct node *temp = start;
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != start);
    printf("\n");
}

void append(struct node **start, int value) {
    if (!*start) {
        struct node *new_node = malloc(sizeof(struct node));
        new_node->data = value;
        new_node->next = new_node->prev = new_node;
        *start = new_node;
        return;
    }
    struct node *last = (*start)->prev;
    struct node *new_node = malloc(sizeof(struct node));
    new_node->data = value;
    new_node->next = *start;
    (*start)->prev = new_node;
    new_node->prev = last;
    last->next = new_node;
}

struct node *find_mid(struct node **start) {
    int count = 0;
    if (!*start) 
        return NULL;
    struct node *temp = *start;
    do {
        count++;
        temp = temp->next;
    } while (temp != *start);

    int mid_index = (count + 1) / 2;
    temp = *start;
    for (int i = 1; i < mid_index; i++)
        temp = temp->next;
    return temp;
}

void merge(struct node **start1, struct node **start2) {
    struct node *temp1 = *start1;
    struct node *temp2 = *start2;
    struct node *last = NULL;
    (*start1)->prev->next = NULL;
    (*start2)->prev->next = NULL;

    if (temp1->data < temp2->data) {
        last = *start1;
        temp1 = temp1->next;
    } else {
        *start1 = *start2;
        last = *start2;
        temp2 = temp2->next;
    }

    while (temp1 != NULL && temp2 != NULL) {
        if (temp1->data < temp2->data) {
            last->next = temp1;
            temp1->prev = last;
            last = temp1;
            temp1 = temp1->next;
        } else {
            last->next = temp2;
            temp2->prev = last;
            last = temp2;
            temp2 = temp2->next;
        }
    }

    if (temp1) {
        last->next = temp1;
        temp1->prev = last;
    }

    if (temp2) {
        last->next = temp2;
        temp2->prev = last;
    }

    while (last->next != NULL)
        last = last->next;

    (*start1)->prev = last;
    last->next = *start1;
}

void merge_sort(struct node **start) {
    struct node *last = (*start)->prev;
    if (last == *start)
        return;
    struct node *mid = find_mid(start);

    struct node *start2 = mid->next;
    mid->next = *start;
    (*start)->prev = mid;
    last->next = start2;
    start2->prev = last;

    merge_sort(start);
    merge_sort(&start2);

    merge(start, &start2);

}

int main()
{
    struct node *start1 = NULL;
    struct node *start2 = NULL;

    struct node *start = NULL;
    append(&start, 5);
    append(&start, 6);
    append(&start, 6);
    append(&start, 13);
    append(&start, 6);
    append(&start, 87);
    append(&start, 6);
    append(&start, 10);
    append(&start, 7);
    merge_sort(&start);
    display(start);

    return 0;
}