链表归并排序c++实现

以下是C++实现链表归并排序的示例代码：

// 定义链表节点结构
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 合并两个有序链表
ListNode* merge(ListNode* l1, ListNode* l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;
    
    ListNode* dummy = new ListNode(0);
    ListNode* curr = dummy;
    
    while (l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            curr->next = l1;
            l1 = l1->next;
        } else {
            curr->next = l2;
            l2 = l2->next;
        }
        curr = curr->next;
    }
    
    if (l1 != NULL) curr->next = l1;
    if (l2 != NULL) curr->next = l2;
    
    return dummy->next;
}

// 归并排序
ListNode* mergeSort(ListNode* head) {
    if (head == NULL || head->next == NULL) return head;
    
    ListNode* slow = head;
    ListNode* fast = head->next;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    ListNode* secondHead = slow->next;
    slow->next = NULL;
    
    ListNode* l1 = mergeSort(head);
    ListNode* l2 = mergeSort(secondHead);
    
    return merge(l1, l2);
}