使用C#在LinkedList中进行循环检测

Question

在访谈问题中,"实现一种检测循环存在的算法".例如,链表有一个循环,如:

0--->1---->2---->3---->4---->5---->6
                 ?                 |
                 |                 ?
                11<—-22<—-12<—-9<—-8

使用Floyd的循环检测,可以通过使用快速和慢速指针来解决此问题.我应该尝试比较

一个.链接的节点值,即

if (fast.data == slow.data) 
    break;

快速和慢速的类型 Link

class Link
{
    int IData {get; set;}
    Link Next {get; set;}
}

要么

湾 他们是否指向相同的参考,即if (fast == slow)

谢谢.

Answer 1

您应该只比较节点本身.毕竟,有一个包含重复数据的链表是合理的,而实际上没有一个循环.

我会称它们为节点而不是链接.链接只是从一个节点到下一个节点或前一个节点的引用 - 特别是,没有与链接相关联的数据,仅与节点相关联.