C语言数据结构 链表与归并排序实例详解

链表介绍

链表是一种数据结构，它对于存储数据是动态而灵活的。它可以根据我们的需要动态的分配内存空间。链表是由先后相连的数据单元（结点）组成，每个结点都包含了下一结点的地址信息，最后一个结点的地址信息为NULL。链表按照操作方式可以分为单向链表、双向链表与循环链表等几种类型。

归并排序原理

归并排序是一种分治思想的算法，基本步骤依次是分割、排序和合并。分割：将数组分成左右两个部分，再将左右两边分别继续重复分割，直到分不出为止；排序：利用递归对子数组进行排序；合并：将排好序的两个子数组进行有序合并，从而使整个数组有序。

链表的归并排序实现

以下代码演示了链表的归并排序实现：

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

ListNode* merge2Lists(ListNode *l1, ListNode *l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;
    if (l1->val < l2->val) {
        l1->next = merge2Lists(l1->next, l2);
        return l1;
    } else {
        l2->next = merge2Lists(l1, l2->next);
        return l2;
    }
}

ListNode* mergeSort(ListNode* head) {
    if (head == NULL || head->next == NULL) return head;
    ListNode *fast = head, *slow = head, *prev = NULL;
    while (fast != NULL && fast->next != NULL) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    prev->next = NULL;
    ListNode *left = mergeSort(head);
    ListNode *right = mergeSort(slow);
    return merge2Lists(left, right);
}

其中，merge2Lists 函数是用来合并两个子链表的算法，mergeSort 函数利用递归来对子链表进行归并排序。

示例

以下两个示例分别展示了空链表和非空链表进行归并排序的过程。

空链表示例

ListNode* head = NULL;
head = mergeSort(head);

输出结果为：NULL，即空链表不需要进行归并排序。

非空链表示例

ListNode l5 = { 4, NULL };
ListNode l4 = { 2, &l5 };
ListNode l3 = { 5, &l4 };
ListNode l2 = { 1, &l3 };
ListNode l1 = { 3, &l2 };
ListNode *head = &l1;
head = mergeSort(head);

输出结果为：1->2->3->4->5，即原链表经过归并排序后变成了升序排列的链表。

以上就是关于C语言数据结构 链表与归并排序实例的详细攻略，希望对您有所帮助。