检测链表中是否存在循环的算法

Question

我希望找到一个算法，用于检查具有n个元素的链表的一致性。该链表使用虚拟头（也称为哨兵节点）。该算法需要在O(n)时间内运行，并且可以除了迭代列表所需的空间外，使用O(1)额外空间。列表的大小未知。此外，禁止修改列表。

如果存在指向先前列表项的列表项，则该列表将被视为不一致。

首先我考虑存储第一个元素，然后在比较当前元素与第一个元素时遍历列表。

- Elfie

---

你事先知道 n 吗？ - joop

不要因为列表大小未知就放弃。算法应该能够检查任何大小（或n个元素）的一致性。 - Elfie

那么，在这种情况下，弗洛伊德算法是您可以得到的最佳选择（不使用额外存储）。 - joop

同意joop的观点。弗洛伊德的乌龟和兔算法可以实现你想要的功能。https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare - GrahamS

Answer 1

这个列表提供了一个 Size 属性来告诉你它包含多少个元素（n）而不需要遍历它吗？

如果有，那么一个简单的解决方案可以满足您所有的大O需求，即尝试遍历列表，并在遍历过程中计算元素数量。如果计数超过了列表中预期的元素数量，则说明它有一个循环。

伪代码应该如下所示：

bool isConsistent (List list)
{
    bool consistent = true;
    Node node = list.Sentinel.Next;
    int count = 0;

    while (node != list.Sentinel && consistent)
    {
         count++;

         if (count > list.Size)
             consistent = false;

         node = node.Next;
    }

    return consistent;
}

这个算法的时间复杂度为O(n)，空间复杂度为O(1)。

- GrahamS

---

我刚刚也在考虑同样的想法。如果计数可用，那么这就是正确的答案。你可以利用列表的循环性，在超过计数值时中断。 - Frode

好的@joop，如果没有大小/计数可用，那么我认为弗洛伊德的乌龟和兔子算法可能是正确/预期的解决方案，但OP似乎并不这么认为。 - GrahamS

Answer 2

Floyd的“乌龟和兔子”算法可以满足您的需求，只需要进行小修改即可与您的虚拟头/尾（哨兵）节点一起使用。

以下是伪代码示例：

Floyd's "Tortoise and Hare" algorithm可以解决问题，只需要对其进行微小的修改即可适用于您的虚拟头/尾（哨兵）节点。

以下是我编写的伪代码：

bool IsConsistent (List list)
{
    Node tortoise = list.Sentinel.Next;
    Node hare = tortoise.Next;

    while (tortoise != list.Sentinel && hare != list.Sentinel)
    {
        if (tortoise == hare)
            return false;

        tortoise = tortoise.Next;
        hare = hare.Next.Next;
    }

    return true;
}

- GrahamS

---

我考虑找出列表中不一致发生的位置。例如：如果没有不一致，我们返回-1，否则返回特定的索引值。我知道这样的算法需要更多的时间，可能是O(n^2)或o(n^2)。因此，为了简化这个问题，让我们假设列表的大小是已知的。 - Elfie

看一下我链接的维基页面。乌龟和兔子算法的其余部分描述了如何找到循环的索引（μ）和循环的长度（λ）。 - GrahamS

我为这个问题添加了第二个答案。您能否请看一下？ - Elfie

Answer 3

你需要一些RAM，如果在链表中的每个项上没有Visited属性。如果有Visited属性，你需要在运行算法之前先清除它。这可能不符合你的大O要求。

“指向前一个列表项”是什么意思不太清楚。是按引用相等（对象）还是相同的值/属性值集合（结构体）？我假设是引用。下面的代码可以很容易地修改以处理结构体。

static void Main(string[] args)
{
    var list = BuildALinkedListFromSomeData();
    var isConsitent = IsConsistent(list);
}

static bool IsConsistent(LinkedList<Item> list)
{ 
    var visited = new List<LinkedListNode<Item>>()
    var runner = list.First;
    while(runner != null)
    {
        if (visited.Contains(runner))
            return false;
        visited.Add(runner);
        runner = runner.Next;
    }
    return true;
}

一种O(n)的解决方案，使用已经使用存储空间的现有数字VisitCounter（不需要额外的存储空间）：

static bool IsConsistent(LinkedList<Item> list)
{
    var runner = list.First;
    if (runner == null)
        return false;  // Assume consistent if empty

    var consistent = true; 
    var runId = runner.Value.VisitCount;
    while (runner != null)
    {
        // Does the traversed item match the current run id?
        if(runner.Value.VisitCount > runId)
        {
            // No, Flag list as inconsistent. It must have been visited previously during this run
            consistent = false;
            // Reset the visit count (so that list is ok for next run)
            runner.Value.VisitCount = runId; 
        }
        // Increase visit count
        runner.Value.VisitCount++;
        // Visit next item in list
        runner = runner.Next;
    }
    return consistent;
}

这会更改列表中项的内容，但不会更改列表本身。如果不允许更改列表项的内容，则当然这也不是一个解决方案。想一想，这根本不是一个可能的解决方案。当列表不一致时，它是循环的，并且最后一个算法永远不会完成 :)

然后，您将不得不从您列表中访问的每个项目向后遍历列表，这将打破您O(n+1)的要求。

结论：如果Count可用，则不是不可能的任务。请参见GrahamS的答案。

- Frode

---

有一个visited属性，但不允许使用它，因为这将涉及对列表进行修改...也考虑过那种方法 :-/ - Elfie

如果您被允许在列表之外创建一个已访问项目的数组，则此代码应该有效。时间复杂度应该是O(n)或更低。 - Frode

“指向前一个列表项”是指以下内容： 众所周知，链表中的每个元素都指向列表的下一个元素。想象一下，在列表中有一个索引为“a”的元素，如果该元素指向另一个索引较低的元素“b”（a < b），则该列表不一致。 - Elfie

@GrahamS 关于存储需求，您需要O(n)的空间来遍历列表，并且额外获得O(1)的空间来编写此算法。如果我们存储第二个已访问节点列表，那么我们的存储需求是否超出了允许范围？ - Elfie

这样做没有意义，@Snelfie。创建一个第二个已访问元素的列表需要随列表大小增长的存储空间，因此它不是O(1)的。 - GrahamS

Answer 4

这是我对第二个问题的解决方案。

IsConsistent(LinkedList<Item> list) :N
    slow = List.Sentinel.next :Element
    fast = slow.next :Element
    isConsistent = true :boolean
    while(fast != list.Sentinel && fast.next != list.Sentinel && isConsistent) do
        if(slow == fast)
            isConsistent = false
        else 
            slow:= slow.next
            fast:= fast.next.next 
    od
    if(isConsistent)
        return 0
    else
        position = 0 : N
        slow:= list.Sentinel
        while(slow != fast) do
            slow:= slow.next
            fast:= fast.next
            position:= position + 1
        od
        return position

- Elfie

---

当第一个while循环找到一个循环时，您应该仅执行第二个while循环以查找循环的位置，否则它将永远不会终止，因为如果没有循环，slow永远无法等于fast。 - GrahamS

看起来更好了。如果isConsistent返回早期，你实际上不需要else子句，但是保留它也可以。我可能会将函数重命名为FindCyclePosition之类的名称，并将返回类型更改为N。 - GrahamS

Answer 5

基本上，指向前一个项目意味着在列表内部有一个循环。在这种情况下，循环检查似乎是合适的。

- fcat

---

很明显我需要检查一个循环。没有循环就没有不一致性。问题在于，在带虚拟头节点的链表中，总会有一个循环。那么我如何找出是否只有由虚拟头节点创建的循环，或者还有另一个循环导致了不一致性呢？ - Elfie

哑节点指向链表的第一个元素，而列表的最后一个元素则指回哑节点。 - Elfie

Answer 6

一开始我没有考虑使用list.Sentinel。现在我有了一个新的想法。

IsConsistent(LinkedList<Item> list) :boolean
    slow = List.Sentinel.next :Element
    fast = slow.next :Element
    while(slow != list.Sentinel && fast != list.Sentinel) do
        if(slow == fast) return false
        else 
              slow:= slow.next
              fast:= fast.next.next 
    od
    return true

- Elfie

---

这更或多或少是乌龟和兔子算法的开始，但OP似乎在问题中拒绝了它。https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare - GrahamS

这也是微不足道的。 (丑陋的!) headnode / sentinel 只是一个小细节。@GrahamS：这就是 OP ... - joop

为什么要检查 slow 是否为空？这种情况会在什么时候发生？使用哨兵节点应该避免出现空值，所以 slow 应该直接从 Sentinel.next 开始。而且为什么要在循环中检查其他条件？你只需这样做：while (slow != list.Sentinel && fast != list.Sentinel)。 - GrahamS

@GrahamS，您说使用哨兵可以避免空值。请想象一下列表为空，您初始化slow = list.Sentinel.next。这会导致slow被初始化为list.Sentinel吗？ 如果我没有错的话：当列表为空时，哨兵指向自己... - Elfie

是的，如果列表为空，则slow和fast都将初始化为list.Sentinel，因此while循环不会执行，函数将返回true。 - GrahamS

我已经添加了一个答案，展示了我如何将其写出来，因为这比在评论中解释更容易。 - GrahamS