单链表Mergesort结果正确但存在内存泄漏问题排查

结合你的需求（merge原地合并无新节点、mergesort生成新链表不修改原链表），内存泄漏大概率出在新链表节点的分配与回收环节，以下是具体排查方向：

1. 检查mergesort的节点复制逻辑 #

因为要求不修改输入链表，你必然需要先复制原链表的所有节点来生成新链表的初始结构。如果出现以下情况会导致泄漏：

• 复制节点时，中途出现异常或分支跳转，未及时释放已复制的节点
• 归并排序完成后，返回的新链表没有被调用者正确释放（测试用例可能仅验证排序结果，未检查内存回收）
• 拆分复制后的链表时，某个子链表的节点指针被覆盖，导致部分节点丢失无法访问和释放

2. 排查merge函数的原地操作是否隐含内存泄漏 #

虽然merge要求原地合并不创建新节点，但要注意：

• 如果mergesort中错误地对原链表节点进行拆分（违反“不修改输入链表”要求），同时又复制了节点，可能导致原节点与复制节点混淆，出现未释放的复制节点
• 原地合并时，是否有临时指针未正确处理，导致某个节点的引用丢失？比如合并过程中覆盖了节点的next指针，却未保存原指针指向的节点，导致该节点成为孤儿节点

3. 边界场景的内存处理 #

重点检查这些情况：

• 空链表：是否在空输入时错误分配了节点？
• 单节点链表：复制或拆分时是否有多余的内存分配？
• 递归终止条件：mergesort的递归退出时，是否有未释放的临时节点？

4. 结合Valgrind报告定位 #

根据Valgrind的泄漏信息（比如泄漏的内存地址、分配点），找到对应的代码行：

• 如果泄漏点是节点分配的位置，检查该节点是否在后续排序过程中被正确链接到最终新链表，或是否在分支中被遗漏释放
• 如果是递归调用中的泄漏，检查递归栈中每个层次的节点是否都被正确处理

举个常见错误示例：复制链表时，仅复制节点但未正确处理尾节点的next指针；或拆分链表时，某个子链表的末尾节点未置空，导致后续无法遍历释放所有节点。

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