C++单链表归并排序代码异常：Split函数在Merge_Sort中调用失效

看起来你的问题核心出在Split函数的逻辑不符合归并排序的要求，再加上递归过程中指针处理不当，导致单独测试Split正常，但嵌入归并排序后完全失效。咱们一步步拆解：

1. 你的Split函数逻辑根本不对 #

归并排序要求把链表拆成前后两个长度近似相等的子链表，但你当前的Split是用check布尔值交替把节点分配给h1和h2——这种拆分方式会让子链表的元素是原链表的奇偶位节点，完全不是归并排序需要的“连续子序列”。单独测试时，你可能只是验证了节点被分到两个链表，但放到递归排序里，子链表本身的元素顺序是混乱的，最终合并结果自然错误。

2. 原链表指针被意外修改 #

你在Split里直接修改了传入的H指针（H = H->next），而Merge_Sort是递归调用的，这会导致递归过程中原链表的头指针被篡改，后续递归拿到的是已经被移动过的H，处理的是不完整的链表片段。

3. 节点的next指针未正确断开 #

如果你用AddLastNode把节点加到子链表末尾时，没有把该节点的next置为NULL，那么节点仍然会指向原链表的下一个节点，导致子链表互相引用、结构混乱，最终排序结果彻底错误。

修正方案 #

第一步：重写Split函数（用快慢指针拆分成前后两半） #

这是归并排序拆分链表的标准做法，能准确找到链表中间节点，断开成两个独立子链表：

void Split(node* H, node*& h1, node*& h2) {
    if (H == nullptr || H->next == nullptr) {
        h1 = H;
        h2 = nullptr;
        return;
    }

    node* slow = H;
    node* fast = H->next;

    // 快指针走两步，慢指针走一步，最终slow停在中间节点
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 拆分成前后两个子链表
    h1 = H;
    h2 = slow->next;
    // 关键：断开前半部分和后半部分的连接
    slow->next = nullptr;
}

第二步：修正Merge_Sort的递归逻辑 #

确保递归时不破坏原链表头指针，正确递归排序子链表后再合并：

// 辅助合并两个有序链表的函数
node* Merge(node* h1, node* h2) {
    if (h1 == nullptr) return h2;
    if (h2 == nullptr) return h1;

    node* result = nullptr;
    if (h1->data <= h2->data) {
        result = h1;
        result->next = Merge(h1->next, h2);
    } else {
        result = h2;
        result->next = Merge(h1, h2->next);
    }
    return result;
}

void Merge_Sort(node*& head) {
    // 递归终止条件：空链表或只有一个节点
    if (head == nullptr || head->next == nullptr) {
        return;
    }

    node* h1 = nullptr;
    node* h2 = nullptr;
    // 调用修正后的Split，不会修改原head指针
    Split(head, h1, h2);

    // 递归排序两个子链表
    Merge_Sort(h1);
    Merge_Sort(h2);

    // 合并两个有序子链表，更新原链表头
    head = Merge(h1, h2);
}

第三步：检查AddLastNode（如果必须使用） #

如果你仍然需要用这个函数来添加节点，一定要把新节点的next置空，避免引用原链表的其他节点：

void AddLastNode(node*& head, node* newNode) {
    if (newNode == nullptr) return;
    // 必须置空，否则会带出原链表的后续节点
    newNode->next = nullptr;
    if (head == nullptr) {
        head = newNode;
        return;
    }
    node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    temp->next = newNode;
}

用这个修正后的代码测试你的输入链表H->1->2->8->4->7->6->33->NULL，应该能得到正确的有序链表H->1->2->4->6->7->8->33->NULL。

内容的提问来源于stack exchange，提问作者Damian