知识卡片
链式归并可用重接减少空间
两个有序链表合并时,可以把已有节点按次序重新连接,不必复制到新的线性数组。若再用自底向上的迭代组织各轮合并,可避免递归栈。
原书只介绍这条优化路线,未给完整实现;常数辅助空间还需允许重接输入节点,并单独处理输出及输入所有权。递归版或保留全新结果的版本不能无条件算常数空间。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
可以使用“迭代”替代“递归”来实现链表划分工作,从而省去递归使用的栈帧空间。 ‧ 合并阶段 :在链表中,节点增删操作仅需改变引用(指针)即可实现,因此合并阶段(将两个短有序链 表合并为一个长有序链表)无须创建额外链表。
参考来源
- 位置:《Hello 算法--Go版本》第11章《排序》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;spine 4,归一字符[30213,30322))
- 结论依据:实际链表排序两项方案,明确未展开实现不伪称完成。
- 原始内容:可以使用“迭代”替代“递归”来实现链表划分工作,从而省去递归使用的栈帧空间。 ‧ 合并阶段 :在链表中,节点增删操作仅需改变引用(指针)即可实现,因此合并阶段(将两个短有序链 表合并为一个长有序链表)无须创建额外链表。