用C++实现对链表的排序

在C++中，链表的排序通常会通过迭代或递归的方式实现，因为链表不适合直接插入排序等基于数组的操作。这里我们可以使用常见的排序算法，如冒泡排序、插入排序、归并排序或者快速排序（后者需要额外的空间复杂度，但对于链表来说比较高效），其中归并排序是一个常用的适合链表的排序算法。

以下是使用归并排序算法对单向链表进行排序的一个基本步骤：

1. **分解**：将链表拆分为两个相等的部分，直到每个部分只有一个元素或者为空。
2. **合并**：将两个有序的子链表合并成一个更大的有序链表，递归地处理剩余部分，直到整个链表排序完成。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head; // 基准条件

    // 找到中间节点
    ListNode* slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* mid = slow->next;
    slow->next = nullptr;

    // 分割链表
    ListNode* left = sortList(head);
    ListNode* right = sortList(mid);

    // 合并排序后的链表
    return merge(left, right);
}

ListNode* merge(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}