std::list::sort()最省事且稳定高效，但自定义类型排序时比较函数必须接受const引用参数并返回bool；手写双向链表宜用归并排序而非快排，注意指针安全与迭代器失效规则。
用 std::list 自带的 sort() 最省事，但得注意比较函数签名
如果你只是需要一个可排序的双向链表，std::list 就是标准答案——它底层就是双向链表，且 sort() 是稳定排序、时间复杂度 O(n log n)，不依赖随机访问。但容易踩的坑是：自定义类型排序时，传入的比较函数必须接受两个 const 引用参数，返回 bool。
比如对 std::list<int> 排序，直接调用即可：
std::list<int> lst = {3, 1, 4, 1, 5};
lst.sort(); // 升序
对自定义结构体，要写对签名：
struct Node { int val; std::string name; };
std::list<Node> lst = {{3,"a"}, {1,"b"}, {2,"c"}};
lst.sort([](const Node& a, const Node& b) { return a.val < b.val; });
- 错写成
(Node a, Node b)（值传递）会编译失败或效率低下 - 返回非
bool（如int）会导致未定义行为 -
std::list::sort()不接受仿函数对象以外的任何迭代器范围，不能像std::sort那样传 begin/end
手写双向链表排序时，别硬刚快排，归并更合适
手写双向链表（含 prev/next 指针）时，常见误区是照搬数组快排逻辑——找 pivot、交换节点、维护边界。但链表没有 O(1) 下标访问，swap 操作成本高，且分区过程极易断链。
立即学习“C++免费学习笔记（深入）”；
真正适合链表的排序是自底向上的归并排序：利用链表天然的“拆分-合并”能力，无需额外空间（除递归栈），稳定，且避免深递归导致的栈溢出。
- 核心操作是
split()（找中点并断开）和merge()（合并两个有序链表） - 找中点推荐快慢指针法，比计数再遍历更安全（避免长度误判）
- 归并时务必统一使用带头结点（dummy node）写法，大幅降低空指针判断复杂度
- 递归实现要注意尾递归优化不可用，数据量大时建议改用迭代版归并
std::list::sort() 和手写归并性能差异不大，但兼容性差很多
实测在万级元素下，std::list::sort() 和手写迭代归并耗时相差通常在 10% 以内。真正差距在工程层面：
-
std::list::sort()依赖编译器实现（GCC 用迭代归并，MSVC 也是），行为一致、无内存泄漏风险 - 手写链表若没做移动语义支持（
Node(Node&&)），std::move失效，字符串等成员会反复拷贝 - 手写版本很难自然支持 allocator（如内存池），而
std::list可直接传入 - 调试时，
std::list的迭代器失效规则明确；手写链表一旦prev/next错位，gdb里几乎无法追踪
排序后遍历出错？大概率是忘了 std::list 迭代器不支持 + 运算
排序完想取第 k 个元素，写 std::next(lst.begin(), k) 是对的，但有人会误写成 lst.begin() + k——这会编译失败，因为 std::list::iterator 是 BidirectionalIterator，不支持随机访问运算符。
- 正确方式只有
std::advance(it, k)或循环k次++it - 如果频繁按索引访问，说明数据结构选错了——该用
std::vector而不是链表 - 排序后插入新元素不会影响已有迭代器有效性（这是
std::list的优势），但删除节点会使对应迭代器立即失效
链表排序真正的复杂点不在算法本身，而在指针操作的边界条件和迭代器生命周期管理。哪怕只多一个 nullptr 检查遗漏，整个链就可能崩在运行时。
