知识卡片

普通读书笔记卡 · 5654.c.3.b.1.a.1

链式归并可用重接减少空间

理解等级:中级

两个有序链表合并时,可以把已有节点按次序重新连接,不必复制到新的线性数组。若再用自底向上的迭代组织各轮合并,可避免递归栈。

原书只介绍这条优化路线,未给完整实现;常数辅助空间还需允许重接输入节点,并单独处理输出及输入所有权。递归版或保留全新结果的版本不能无条件算常数空间。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      可以使用“迭代”替代“递归”来实现链表划分工作,从而省去递归使用的栈帧空间。 ‧ 合并阶段 :在链表中,节点增删操作仅需改变引用(指针)即可实现,因此合并阶段(将两个短有序链 表合并为一个长有序链表)无须创建额外链表。

    参考来源

    - 位置:《Hello 算法--Go版本》第11章《排序》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;spine 4,归一字符[30213,30322)) - 结论依据:实际链表排序两项方案,明确未展开实现不伪称完成。 - 原始内容:可以使用“迭代”替代“递归”来实现链表划分工作,从而省去递归使用的栈帧空间。 ‧ 合并阶段 :在链表中,节点增删操作仅需改变引用(指针)即可实现,因此合并阶段(将两个短有序链 表合并为一个长有序链表)无须创建额外链表。