我今天接受了一个开发人员职位的面试，并被问到一个有趣的技术问题，我不知道答案。我会在这里问它，看看是否有人可以为我的好奇心提供解决方案。这是一个多部分的问题：
1）给你一个包含 100 个元素（整数和指向下一个节点的指针）的单链表，找到一种方法来检测链表中途是否存在中断或损坏？你可以对链表做任何事情。请注意，您必须在列表中执行此操作，因为它正在迭代，这是在您意识到列表有任何问题之前的验证。
假设链表中的中断在第 50 个元素处，则整数甚至指向下一个节点（第 51 个元素）的指针可能指向一个垃圾值，该值不一定是无效地址。
2）请注意，如果链表中存在损坏，您将如何最大程度地减少数据丢失？
要测试“损坏的”整数，您需要知道有效值的范围是多少。否则，无法确定任何给定（有符号）整数中的值是无效的。因此，假设您对 int 进行了有效性测试，您将始终在迭代到下一个元素之前检查该值。
测试损坏的指针比较棘手 - 首先，您需要做的是在尝试取消引用之前检查指向下一个元素的指针的值，并确保它是有效的堆地址。这将避免分段错误。接下来是验证指针指向的实际上是一个有效的链表节点元素——这有点棘手？也许将指针取消引用到列表元素类/结构中，并测试 int 和“next”指针的有效性，如果它们也很好，那么可以很确定前一个节点也很好。
在 2) 发现损坏的节点后，[如果下一个指针损坏] 你应该立即将前一个节点的“下一个指针”设置为“NULL”，将其标记为列表的末尾，并记录你的错误等等如果损坏只是整数值，而不是“下一个”元素指针，那么你应该从列表中删除该元素并将前一个和后一个节点链接在一起 - 因为不需要抛出在这种情况下，列表的其余部分！
如果您在设计时知道损坏可能成为一个关键问题，您可以将“魔术值”作为字段添加到节点数据结构中，以便您识别某些数据是否可能是节点。甚至可以通过内存搜索节点。
或者加倍一些链接信息，即在每个节点中存储下一个节点之后的节点地址，这样如果一个链接坏了你可以恢复。
我看到的唯一问题是您必须避免分段错误。
对于第一部分 - 重载 new 运算符。每当分配一个新节点时，请在该节点之前和之后分配一些额外的空间，并将一些已知值放在那里。在遍历中，可以检查每个节点是否在已知值之间。
如果你可以对链表做任何事情，你可以做的就是计算每个元素的校验和并将其存储在元素本身上。通过这种方式，您将能够检测到损坏，即使它是元素上的单个位错误。
为了最大限度地减少数据丢失，也许您可以考虑将 nextPtr 存储在前一个元素中，这样如果您的当前元素已损坏，您总是可以从前一个元素中找到下一个元素的位置。
这是一个简单的问题，有几个可能的答案。每个都在稳健性和效率之间进行权衡。由于提高健壮性是所问问题的先决条件，因此有一些可用的解决方案既牺牲时间（列表遍历速度，以及节点的插入速度和删除速度），也牺牲空间（每个节点存储的额外信息）。现在问题已经说明，这是一个长度为100的固定列表，这种情况下链表的数据结构是最不合适的。为什么不让这个谜题更具挑战性，并说列表的大小是先验未知的？
由于元素的数量 (100) 是已知的，因此第 100 个节点必须包含一个空指针。如果确实如此，则该列表很有可能是有效的（这不能保证，例如，如果第 99 个节点已损坏并指向某个全为零的内存位置）。否则，有一些问题（这可以作为事实返回）。
upd：此外，每一步都可以查看delete如果给定指针将使用的某些结构，但由于使用delete本身在任何意义上都不安全，这将是特定于实现的。