链表和哨兵节点

Question

所以我在作业中被要求在不使用 sentinal node 的情况下对 2 个不同的排序循环链表进行合并排序，而且列表可以为空，我的问题是什么是 sentinal node第一名？

Answer 1

哨兵节点是不包含实际数据的节点 - 它只是为了方便实现而存在。

因此，一个包含 4 个实数元素的列表可能会有一个或多个额外的节点，总共有 5 或 6 个节点。

这些额外的节点可能是占位符（例如标记开始合并的位置）、指示列表头部的伪节点或算法设计者可以想到的任何其他内容。

Answer 2

哨兵节点是您添加到代码中以避免使用特殊代码处理退化的节点。例如，对于合并排序，您可以将 value = INFINITY 的节点添加到要合并的两个列表的末尾，这保证一旦您到达列表的末尾，您就不能超出它，因为该值始终大于（或等于）另一个列表中的值。

所以如果你不使用哨兵，你必须编写代码来处理这个问题。在你的合并例程中，你应该检查你是否已经到达终点..

Answer 3

哨兵节点是链表和树中遍历路径的终结者。它不保存或引用由数据结构管理的任何数据。好处之一是减少算法的复杂性和代码 size.In 你的情况复杂性，代码大小将增加，操作速度将降低。