基于链表实现的归并排序未按预期运行问题排查

问题根因 #

你的代码功能错误主要有3处：

1. merge() 函数返回值错误
   你在merge中新建了哨兵节点作为临时头，遍历用的tmp最终指向合并后链表的最后一个节点，但你返回了tmp而不是合并后链表的实际头节点，同时临时哨兵节点没有释放会造成内存泄漏。
2. 递归调用sort_merge()没有接收返回值
   sort_merge(beg)和sort_merge(end)执行后，会返回子链表排序后的新头节点，但你没有将返回值赋值给beg和end，导致后续merge的还是未排序的子链表旧头。
3. 顶层sort()函数没有更新链表的头节点
   你调用sort_merge(l.sentinel)后，没有将排序后返回的新头赋值给l.sentinel，原链表的头还是初始的5节点，而split操作已经把原来的链表从5后面断开了，所以打印只会输出5。

修正后的核心代码 #

// 修正merge函数
Link* merge(Link* beg, Link* end) {
    Link* dummy = new Link;
    Link* tmp = dummy;
    for (; beg != NULL && end != NULL; tmp = tmp->next) {
        if (beg->data < end->data) {
            tmp->next = beg;
            beg = beg->next;
        } else {
            tmp->next = end;
            end = end->next;
        }
    }
    tmp->next = (beg == NULL) ? end : beg;
    Link* res = dummy->next;
    delete dummy; // 释放临时哨兵节点避免内存泄漏
    return res;
}

// 修正sort_merge函数
Link* sort_merge(Link* sentinel) {
    if (sentinel == NULL || sentinel->next == NULL)
        return sentinel;
    Link* beg, * end;
    split(sentinel, beg, end);
    // 接收递归排序后的新头
    beg = sort_merge(beg);
    end = sort_merge(end);
    return merge(beg, end);
}

// 修正sort函数
void sort(LinkList &l) {
  // 更新链表头为排序后的新头
  l.sentinel = sort_merge(l.sentinel);
}

修正后运行代码即可输出预期的1~5升序结果。

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