代码之家  ›  专栏  ›  技术社区  ›  No Refunds No Returns

是否有人有C代码来修复循环的链接列表?

  •  1
  • No Refunds No Returns  · 技术社区  · 15 年前

    how do you remove a cycle in a single linked list?

    在我编写一些示例代码来完成这个答案所描述的工作之前,是否有人已经有了修复指向自身的单个链接列表的C示例?

    我了解检测部分(乌龟/兔子档),但维修部分对我来说有点模糊。

    2 回复  |  直到 15 年前
        1
  •  3
  •   Eric Lippert    15 年前

    您链接到的文章有一些算法,允许您计算具有两个引用的节点,一个引用自列表的开头,另一个引用自应该是列表“结尾”的节点。如果您可以找到那个节点,那么您肯定可以找到应该是列表末尾的节点。找到那个节点。将其“next”引用设置为空。

    我的建议是:在你的白板上画很多很多的框和箭头。通过在板上手动运行它六次来了解算法是如何工作的。一旦你理解了它是如何在视觉上工作的,那么编写代码就会简单得多。(因为这个原因,我的白板上通常塞满了十几种不同颜色的盒子和箭头…)

        2
  •  1
  •   Anon.    15 年前

    你会发现循环的“开始”。这是有多个节点连接到它的节点。

    这些节点中的一个将来自列表的头部—您想让这个单独存在。

    另一个节点是您要更改的节点-通常是使其连接到 null ,指示列表的结尾。