C＋＋链表的排序如何实现

在C++中，链表通常不适合直接使用像数组那样通过索引来快速访问元素，因此排序链表时一般需要遍历整个链表。一种常见的排序算法是归并排序（Merge Sort），它适合于链表操作。以下是使用递归的方式实现归并排序链表的例子：

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

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

    if (l1->val > l2->val) {
        ListNode temp(*l1);
        l1 = l1->next;
        temp.next = merge(l1, l2);
        return &temp;
    } else {
        ListNode temp(*l2);
        l2 = l2->next;
        temp.next = merge(l1, l2);
        return &temp;
    }
}

void sortList(ListNode*& head) {
    if (!head || !head->next) return; // 特殊情况，只有一个元素或为空

    ListNode* slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    slow->next = NULL;

    ListNode* tail = sortList(head);
    head = merge(head, tail);
}