c语言链表排序

链表排序一般采用归并排序或快速排序。

1. 归并排序

归并排序的基本思路是分治法，将链表分成若干个子链表，对每个子链表进行排序，然后合并子链表，直到最后只剩下一个有序链表。具体实现如下：

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

// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;

    ListNode *head = NULL;
    ListNode *tail = NULL;

    // 将较小的结点作为头结点
    if (l1->val < l2->val) {
        head = l1;
        l1 = l1->next;
    }
    else {
        head = l2;
        l2 = l2->next;
    }

    // 遍历两个链表，依次取出较小的结点
    tail = head;
    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 if (l2 != NULL) {
        tail->next = l2;
    }

    return head;
}

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

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

    // 将链表分成两个子链表
    ListNode *head1 = head;
    ListNode *head2 = slow->next;
    slow->next = NULL;

    // 递归排序两个子链表
    head1 = sortList(head1);
    head2 = sortList(head2);

    // 合并两个子链表，返回头结点
    return mergeTwoLists(head1, head2);
}

2. 快速排序

快速排序的基本思路是选取一个元素作为基准值，将链表分成小于基准值和大于等于基准值的两部分，然后递归地对两部分进行快速排序。具体实现如下：

// 获取链表结点数量
int getListLength(ListNode *head) {
    int count = 0;
    while (head != NULL) {
        count++;
        head = head->next;
    }
    return count;
}

// 快速排序
ListNode* quickSort(ListNode *head, ListNode *tail) {
    if (head == NULL || head == tail) {
        return head;
    }

    // 将链表分成小于基准值和大于等于基准值的两部分
    ListNode *pivot = head;
    ListNode *p = head;
    ListNode *q = head->next;
    while (q != tail) {
        if (q->val < pivot->val) {
            p = p->next;
            int tmp = p->val;
            p->val = q->val;
            q->val = tmp;
        }
        q = q->next;
    }
    int tmp = p->val;
    p->val = pivot->val;
    pivot->val = tmp;

    // 递归地对两部分进行快速排序
    quickSort(head, p);
    quickSort(p->next, tail);

    return head;
}

// 快速排序入口函数
ListNode* sortList(ListNode* head) {
    int len = getListLength(head);
    return quickSort(head, NULL);
}