如何在C++ list上使用while循环实现归并排序的合并逻辑？

std::list为双向链表结构，不支持随机下标访问，我们可以用双向迭代器替代数组下标实现合并逻辑，对应关系完全匹配你提供的数组版代码，还可以配合list的节点转移方法splice避免元素拷贝，提升性能。

合并逻辑代码实现 #

假设你已经拆分得到两个有序子列表left_list、right_list，需要合并到目标列表res_list中：

#include <list>

template<typename T>
void merge_list(std::list<T>& res_list, std::list<T>& left_list, std::list<T>& right_list) {
    // 对应数组版的i=0、j=0、k=l，用迭代器替代下标
    auto left_it = left_list.begin();
    auto right_it = right_list.begin();
    auto res_it = res_list.begin();

    // 对应第一个while：同时遍历左右子列表，取较小值放入目标位置
    while (left_it != left_list.end() && right_it != right_list.end()) {
        if (*left_it <= *right_it) {
            // splice直接转移节点，不需要拷贝元素，等价于array[k] = larr[i]
            res_list.splice(res_it, left_list, left_it++);
        } else {
            res_list.splice(res_it, right_list, right_it++);
        }
        res_it++;
    }

    // 对应第二个while：左列表剩余元素全部插入
    while (left_it != left_list.end()) {
        res_list.splice(res_it, left_list, left_it++);
        res_it++;
    }

    // 对应第三个while：右列表剩余元素全部插入
    while (right_it != right_list.end()) {
        res_list.splice(res_it, right_list, right_it++);
        res_it++;
    }
}

关键说明 #

• 如果你不需要优化性能，也可以直接用赋值逻辑实现，把splice行替换为*res_it = *left_it; left_it++;即可，逻辑和数组版完全一致
• C++标准库的std::list已经内置了有序合并方法merge()，可以直接调用left_list.merge(right_list)完成两个有序列表的合并，无需手动实现

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