递归拆分迭代合并的链表归并排序返回错误结果，求排查方案

问题根因 #

你的代码错误出在两个有序链表的合并逻辑：

• 没有维护已合并链表的尾指针，每次只将当前较小节点指向另一链表的头部，没有和之前已合并的节点建立链接，导致部分节点被直接丢弃（你测试用例里的4、5就是这么丢失的）
• 循环结束后没有将未遍历完的剩余链表段直接接到合并结果尾部，极端场景会丢失后半段数据

修复后的完整代码 #

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/

ListNode* Solution::sortList(ListNode* A) {
    ListNode * head = A;
    if(!head || !head->next)
    {   
        return head;
    }
    // 快慢指针找中点拆分逻辑无问题
    ListNode * slow = head, * fast = head;
    while(fast->next && fast->next->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    ListNode * right = slow->next;
    slow->next = NULL;

    ListNode* leftSorted = sortList(head);
    ListNode* rightSorted = sortList(right);

    // 合并逻辑修复：引入哑节点简化边界处理
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while(leftSorted && rightSorted)
    {
        if(leftSorted->val < rightSorted->val)
        {
            tail->next = leftSorted;
            leftSorted = leftSorted->next;
        }
        else
        {
            tail->next = rightSorted;
            rightSorted = rightSorted->next;
        }
        tail = tail->next; // 已合并链表尾指针后移
    }
    // 拼接剩余未遍历的节点
    tail->next = leftSorted ? leftSorted : rightSorted;
    return dummy.next;
}

原有合并逻辑错误复现（以你给出的测试用例为例） #

你的测试输入拆分到合并阶段会得到两个有序链表[3,4,5]和[1,2,6]，用原有逻辑执行时：

1. 初始head=3、temp=1，ans被赋值为1，temp移动到2，1的next设为3
2. 下一轮判断3>2，ptr=2，temp移动到6，2的next设为3，此时没有将2挂到已合并的节点1后面，1的next仍指向3
3. 后续遍历4、5节点时，同样没有将节点挂到已合并链表尾部，最终导致4、5节点完全从结果链中丢失，就出现了你得到的错误返回结果。

内容的提问来源于stack exchange，提问作者At-U