单链表归并排序c语言

单链表归并排序的C语言实现步骤如下：
1. 定义单链表结构体和归并排序函数
2. 实现归并排序函数，其中包括以下步骤：
a. 如果链表为空或只有一个节点，直接返回
b. 使用快慢指针将链表分成两个子链表
c. 递归调用归并排序函数对两个子链表进行排序
d. 合并两个已排序的子链表

下面是单链表归并排序的C语言代码实现：

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

// 定义单链表结构体
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 归并排序函数
ListNode* mergeSortList(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    // 使用快慢指针将链表分成两个子链表
    ListNode *slow = head, *fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode *mid = slow->next;
    slow->next = NULL;
    // 递归调用归并排序函数对两个子链表进行排序
    ListNode *left = mergeSortList(head);
    ListNode *right = mergeSortList(mid);
    // 合并两个已排序的子链表
    ListNode *dummy = (ListNode*)malloc(sizeof(ListNode));
    ListNode *cur = dummy;
    while (left != NULL && right != NULL) {
        if (left->val < right->val) {
            cur->next = left;
            left = left->next;
        } else {
            cur->next = right;
            right = right->next;
        }
        cur = cur->next;
    }
    cur->next = (left != NULL) ? left : right;
    ListNode *newHead = dummy->next;
    free(dummy);
    return newHead;
}

// 测试代码
int main() {
    // 创建链表
    ListNode *head = (ListNode*)malloc(sizeof(ListNode));
    head->val = 4;
    head->next = (ListNode*)malloc(sizeof(ListNode));
    head->next->val = 2;
    head->next->next = (ListNode*)malloc(sizeof(ListNode));
    head->next->next->val = 1;
    head->next->next->next = (ListNode*)malloc(sizeof(ListNode));
    head->next->next->next->val = 3;
    head->next->next->next->next = NULL;
    // 归并排序
    ListNode *newHead = mergeSortList(head);
    // 输出排序后的链表
    while (newHead != NULL) {
        printf("%d ", newHead->val);
        newHead = newHead->next;
    }
    printf("\n");
    return 0;
}