检查链表循环的算法

Question

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

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

Answer 1

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

Answer 2

如果链接列表中的每个项目都没有访问属性，则需要一些 RAM。如果您有一个 Visited 属性，您首先需要在运行算法之前将其清除。这可能不符合您的大 O 要求。

不清楚 "points at previous list item" 是什么意思。等于引用（对象）或 value/set 的属性值（结构）？我假设参考。下面的代码也可以轻松修改以处理结构。

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 space（不需要额外的存储空间）：

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 的回答

Answer 3

列表是否提供了一个 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) 存储。

Answer 4

一开始没想过用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

Answer 5

Floyd's "Tortoise and Hare" algorithm 做你需要的，只需要一个小的修改就可以与你的虚拟 head/tail（哨兵）节点一起工作。

这是我编写伪代码的方式：

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

Answer 6

这是我对第二个问题的解答。

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

检查链表循环的算法

Algorithm to check a linked-list for loops

algorithm

performance

linked-list

singly-linked-list

sentinel