写一份C语言带表头结点单链表的归并排序函数代码

在C语言中，我们通常不会直接对单链表进行原地的归并排序（因为链表不是随机访问数据结构，不适合快速查找和交换元素），而是会先将其转换为数组或其他可排序的数据结构，然后再进行归并排序。但是，如果你只是想了解如何在内存中操作两个已排序的链表节点合并成一个有序链表，这里是一个示例，展示如何合并两个单链表的节点：

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

typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 合并两个已排序链表
ListNode* mergeSortedLists(ListNode* l1, ListNode* l2) {
    ListNode dummy = {0, NULL}; // 创建虚拟头节点，方便后续处理
    ListNode* tail = &dummy;    // 当前尾指针

    while (l1 != NULL && l2 != NULL) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    // 如果其中一个链表还有剩余元素，则将剩余部分连接到结果链表末尾
    if (l1 != NULL) {
        tail->next = l1;
    } else {
        tail->next = l2;
    }

    return dummy.next; // 返回合并后的实际链表头节点
}

// 假设你已经有了两个已排序的链表节点作为输入
void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr != NULL) {
        printf("%d ", curr->val);
        curr = curr->next;
    }
    printf("\n");
}

// 示例用法
int main() {
    // 创建两个已排序的小链表
    ListNode* list1 = create_sorted_list({1, 3, 5});
    ListNode* list2 = create_sorted_list({2, 4, 6});

    ListNode* mergedList = mergeSortedLists(list1, list2);

    printList(mergedList);  // 输出：1 2 3 4 5 6

    free(list1);
    free(list2);
    free(mergedList);  // 别忘了释放内存

    return 0;
}

请注意，上述代码并没有真正实现归并排序，而是在内存中合并两个已经排序好的链表。如果要实现整个归并排序过程，你需要首先将链表转换为数组，然后递归地分割、排序和合并子数组，再将结果合并回链表。这将涉及到更复杂的逻辑和更多的代码。