linux内核链表实现排序

#include <linux/list.h>

// 定义链表节点结构
struct ListNode {
    int data;
    struct list_head list;
};

// 合并两个有序链表
static struct list_head* merge_sorted_lists(struct list_head* head1, struct list_head* head2) {
    struct list_head* result = NULL;
    struct list_head** tail_ptr = &result;

    while (!list_empty(head1) && !list_empty(head2)) {
        struct list_head* selected;
        if (list_entry(head1->next, struct ListNode, list)->data <= list_entry(head2->next, struct ListNode, list)->data) {
            selected = head1->next;
            head1 = head1->next;
        } else {
            selected = head2->next;
            head2 = head2->next;
        }
        *tail_ptr = selected;
        tail_ptr = &selected->next;
    }

    *tail_ptr = !list_empty(head1) ? head1 : head2;
    return result;
}

// 归并排序主函数
static struct list_head* merge_sort(struct list_head* head) {
    if (list_empty(head) || list_is_singular(head)) {
        return head;
    }

    struct list_head* slow = head;
    struct list_head* fast = head->next;

    while (!list_empty(fast) && !list_empty(fast->next)) {
        slow = slow->next;
        fast = fast->next->next;
    }

    struct list_head* mid = slow->next;
    slow->next = NULL;

    return merge_sorted_lists(merge_sort(head), merge_sort(mid));
}

// 使用示例
int main() {
    // 初始化链表并添加节点
    // ...

    // 排序链表
    list_head* sorted_list = merge_sort(&head);

    // 打印排序后的链表
    // ...

    return 0;
}