C++链表归并排序实现时左半区无限递归问题排查与修正

• 核心故障点在getmid函数的快慢指针实现错误，直接导致链表拆分失效：
  • 原实现的指针遍历逻辑，在遇到长度为2个节点的链表时，会直接把第二个节点判定为中点
  • 拆分流程中执行mid->link = NULL时，因为中点是后一个节点，前半段链表的尾部指针（也就是第一个节点的next）没有被截断，导致左子链表和传入的父链表长度完全一致
  • 每次拆分得到的右半区头节点mid->link永远是NULL，根本无法触发右半区的排序递归，递归流程会一直卡在左半区的处理环节，形成死循环
• 附加逻辑缺陷：mergesort函数会返回排序完成后的新链表头节点，但主函数调用时没有接收这个返回值，全局head指针始终指向未排序的旧链表，就算排序逻辑修正，最终打印结果也不正确
• 无影响的冗余逻辑：merge函数的空值判断分支存在永远不会触发的else返回NULL，不影响程序运行但逻辑冗余

调整getmid的指针遍历逻辑 #

修改快慢指针的初始值和循环终止条件，保证返回的中点是前半段链表的尾节点，拆分后左右两个子链表长度至少为1，避免拆分前后链表长度完全一致的问题：

Node* getmid(Node* temp)
{
    if (temp == NULL || temp->link == NULL) {
        return temp;
    }
    Node* slow = temp;
    Node* fast = temp->link;
    // 快指针每次走两步，避免越界
    while (fast != NULL && fast->link != NULL) {
        slow = slow->link;
        fast = fast->link->link;
    }
    return slow;
}

修正后对2节点链表的拆分效果：传入8->23链表时，快指针初始指向23，因为23的后继为NULL，循环不触发，返回慢指针（也就是8）作为中点。拆分时左子链表为8，右子链表为23，设置mid->link = NULL后，两个子链表长度都为1，可正常触达递归终止条件，不会出现死循环。

修正主函数的调用逻辑 #

接收mergesort返回的排序后链表头，赋值给全局head指针，保证display函数遍历的是排序完成后的链表：

// 原错误写法：mergesort(head);
head = mergesort(head);

（可选）精简merge函数冗余逻辑 #

简化空值判断分支，去掉永远无法触发的else返回逻辑：

Node* merge(Node* left, Node* right)
{
    Node* res = NULL;
    if (left == NULL) return right;
    if (right == NULL) return left;
    if (left->data < right->data) {
        res = left;
        res->link = merge(left->link, right);
    } else {
        res = right;
        res->link = merge(left, right->link);
    }
    return res;
}

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