双向链表归并问题：合并未预排序DLists时归并函数功能失效

云原生阿岚

2026-9-24

问题根因

递归逻辑存在数据丢失问题：你在每一层递归中都会新建一个空链表ls，向其中插入1个元素后，直接将下一层递归返回的结果赋值给ls，导致当前层插入的元素被完全覆盖。再加上你写的判断逻辑每次都会优先取ls1的头节点（因为ls1第一个元素9小于ls2第一个元素12，后续ls1剩余头节点5、1、4、3也都小于12），直到ls1被取空后直接返回ls2，最终结果就是ls1的原有顺序拼接ls2的原有顺序，和你给出的实际输出完全匹配。
归并逻辑适用前提不符：你当前写的每次取两个链表头较小值的逻辑，仅支持两个本身已经升序排列的链表的合并。如果你的需求是合并后得到有序链表，要么先对两个输入链表分别做排序再执行归并，要么将两个链表所有元素汇总后统一排序。

修复方案

场景1：仅需合并两个链表所有元素，无需保证顺序

直接修改递归逻辑，避免当前层插入的元素被覆盖即可，修改后的归并函数如下：

DoublyLinkedList MergeSort(DoublyLinkedList &ls1, DoublyLinkedList &ls2)
{
    DoublyLinkedList ls;
    Initial(ls);
    if(isEmpty(ls1))
        return ls2;
    if(isEmpty(ls2))
        return ls1;
    if(ls1.head->data <= ls2.head->data)
    {
        InsertLast(ls, ls1.head->data);
        RemoveFirst(ls1);
    }
    else
    {
        InsertLast(ls, ls2.head->data);
        RemoveFirst(ls2);
    }
    // 不再直接覆盖ls，将递归返回的结果追加到当前ls末尾
    DoublyLinkedList subLs = MergeSort(ls1, ls2);
    DNode *p = subLs.head;
    while(p != nullptr) {
        InsertLast(ls, p->data);
        p = p->next;
    }
    return ls;
}