检查循环链接列表的算法

Question

我想找一种checks a linked-list with n elements for consistency算法。链接列表使用dummy head (也称为哨兵节点)。该算法需要run in O(n) time，除了迭代列表所需的空间外，还允许use O(1) extra space。列表的size is unknown。另外，它是forbidden to modify the list。

如果存在指向前一个列表项的列表项，则列表计算为不一致。首先，我考虑存储第一个元素，然后遍历列表，同时将当前元素与第一个元素进行比较。

Answer 1

这是我对第二个问题的解决办法。

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

Answer 2

该列表是否提供了一个Size属性，该属性告诉您它包含多少个元素而不遍历它？

如果这样做了，那么满足所有大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)存储。

Answer 3

弗洛伊德的“龟兔”算法可以满足您的需要，只需要进行一次小的修改就可以处理虚拟头/尾(哨兵)节点。

下面是我如何编写伪代码：

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;
}