c语言如何实现链表的排序

首先需要声明一个链表节点的结构体，包括节点中存储的数据和指向下一个节点的指针。然后使用各种排序算法，如冒泡排序、插入排序、选择排序等等，对链表进行排序。具体实现方式与排序算法有关，可以自行查找相关资料学习。

相关问题

C语言指针链表排序

实现 C 语言指针链表排序的一种常用方法是使用冒泡排序法。具体实现步骤如下：

1. 定义链表节点结构体，包含一个整数值和一个指向下一个节点的指针。

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

2. 定义一个函数，接收链表头节点的指针，并返回排好序的链表头节点的指针。

struct ListNode* sortList(struct ListNode* head) {
    if (!head || !head->next) {
        return head;
    }
    struct ListNode *p, *q, *end = NULL;
    while (head != end) {
        p = head;
        q = head->next;
        while (q != end) {
            if (p->val > q->val) {
                int tmp = p->val;
                p->val = q->val;
                q->val = tmp;
            }
            p = p->next;
            q = q->next;
        }
        end = p;
    }
    return head;
}

在这个函数中，我们首先判断链表是否为空或只有一个节点，如果是，则直接返回原链表头节点的指针；否则，我们定义两个指针 p 和 q，分别指向头节点和头节点的下一个节点，然后进行冒泡排序，将最大的节点从头节点开始向后冒泡，直到链表尾部。排序结束后，我们将 end 指向最后一个已排序的节点，然后再次从头节点开始进行冒泡排序，直到 end 指向头节点为止。

3. 在主函数中创建一个链表，并调用 sortList 函数进行排序。

int main() {
    struct ListNode n1 = {4, NULL};
    struct ListNode n2 = {2, &n1};
    struct ListNode n3 = {1, &n2};
    struct ListNode n4 = {3, &n3};
    struct ListNode *head = &n4;
    struct ListNode *p = head;
    while (p) {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
    head = sortList(head);
    p = head;
    while (p) {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
    return 0;
}

在这个例子中，我们创建了一个包含 4 个节点的链表，然后调用 sortList 函数进行排序，并打印出排序前后的链表节点值。

C语言实现链表的归并

以下是C语言实现链表归并的示例代码：

#include <stdio.h>
#include <stdlib.h>
// 定义链表结构体
struct ListNode {
    int val;
    struct ListNode *next;
};

// 合并两个有序链表
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    // 定义哨兵节点
    struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
    dummy->next = NULL;
    struct ListNode *cur = dummy;

    // 遍历两个链表，将较小的节点加入新链表中
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }

    // 将剩余的节点加入新链表中
    if (l1) {
        cur->next = l1;
    } else {
        cur->next = l2;
    }

    return dummy->next;
}

// 归并排序
struct ListNode* sortList(struct ListNode* head) {
    if (!head || !head->next) {
        return head;
    }

    // 快慢指针找到链表中点
    struct ListNode *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 分割链表
    struct ListNode *mid = slow->next;
    slow->next = NULL;

    // 递归排序左右两个链表
    struct ListNode *left = sortList(head);
    struct ListNode *right = sortList(mid);

    // 合并两个有序链表
    return mergeTwoLists(left, right);
}

// 创建链表
struct ListNode* createList(int arr[], int n) {
    if (n == 0) {
        return NULL;
    }

    struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;    struct ListNode *cur = head;

    for (int i = 1; i < n; i++) {
        struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
        node->val = arr[i];
        node->next = NULL;
        cur->next = node;
        cur = cur->next;
    }

    return head;
}

// 打印链表
void printList(struct ListNode *head) {
    while (head) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

int main() {
    int arr[] = {4, 2, 1, 3};
    int n = sizeof(arr) / sizeof(int);

    struct ListNode *head = createList(arr, n);
    printf("原链表：");
    printList(head);

    head = sortList(head);
    printf("排序后的链表：");
    printList(head);

    return 0;
}