最佳算法来测试链表是否有循环。

7 浏览
0 Comments

最佳算法来测试链表是否有循环。

如何确定一个链表中是否存在循环的最佳（暂停）算法？

【编辑】如果对时间和空间的渐进复杂度进行分析，那就更好了，这样就可以更好地对答案进行比较。

【编辑】原始问题没有涉及出度大于1的节点，但是有一些讨论。这个问题更接近于“检测有向图中循环的最佳算法”。

0

3 答案

0 Comments

链表中是否存在循环是一个常见的问题，需要找到一个最佳算法来进行判断。下面的内容提供了一种解决方法。

我们可以采用两个指针*p和*q，同时遍历链表LL：

1）指针p每次都会删除前一个节点，并指向下一个节点。

2）指针q每次只会向前移动一个节点。

根据以下条件进行判断：

1）如果指针p指向null而指针q指向某个节点：说明存在循环。

2）如果两个指针都指向null：说明不存在循环。

下面是一个示例代码：

def has_cycle(LL):
    p = LL
    q = LL
    while q is not None and q.next is not None:
        p = p.next
        q = q.next.next
        if p == q:
            return True
    return False

这个算法的原理是使用两个指针在链表上移动，如果存在循环，两个指针最终会相遇。如果不存在循环，指针q会先到达链表的末尾。这种算法的时间复杂度是O(n)，其中n是链表的长度。

通过这个算法，我们可以很方便地判断一个链表是否存在循环，从而避免在处理链表时出现死循环的情况。这对于链表操作的正确性非常重要。

0
0 Comments

链表中是否存在循环是一个常见的问题，解决该问题的最佳算法是使用龟兔赛跑算法（Tortoise and Hare algorithm）。该算法通过使用两个指针在链表中迭代，其中一个指针的速度是另一个指针的两倍，并在每一步比较它们的位置。以下是该算法的代码实现：

node* tortoise = begin;
node* hare = begin;
while (hare && hare->next)
{
    hare = hare->next;
    if (hare == tortoise)
    {
        throw std::logic_error("There's a cycle");
    }
    hare = hare->next;
    if (hare == tortoise)
    {
        throw std::logic_error("There's a cycle");
    }
    tortoise = tortoise->next;
}

该算法的时间复杂度是O(n)，也就是最佳的时间复杂度。

除了算法实现之外，还有一些讨论和补充的内容。其中有人指出代码中的while循环应该改为`while (hare && hare = hare->next)`，以防止迭代超出链表末尾。还某些情况下，只有当链表为空时（即root为空）才需要`while (hare && hare = hare->next)`这样的判断条件，否则定义的while循环会在hare->next返回null时终止。另外，还有人指出在代码中hare = hare->next在循环体内赋值，因此在此处hare可能为null。

此外，还某些情况下了使用顶点着色算法（Vertex coloring）来解决该问题的方法。该方法需要两次遍历链表，一次用于重置颜色，另一次用于检测循环。虽然该方法在每个节点上使用了稍多的内存，但在存在循环的情况下，它比龟兔赛跑算法更快。

最后，有人指出龟兔赛跑算法早在1967年就被Floyd发表了，该算法用于定位循环。而这里的问题只是判断链表中是否存在循环，两种算法的原理相同，但是这种方法更加简单。

总结起来，链表中是否存在循环是一个常见的问题，可以使用龟兔赛跑算法来解决。该算法通过使用两个指针在链表中迭代，其中一个指针的速度是另一个指针的两倍，并在每一步比较它们的位置。该算法的时间复杂度是O(n)，是一种高效的解决方法。

0
0 Comments

问题：最佳算法来检测链表是否有循环

在检测链表是否有循环的问题中，我们可以通过以下方法来解决：

1. 预设条件：在添加或删除节点时，跟踪链表的大小（更新链表的大小）。

2. 循环检测：

- 遍历链表时保持一个计数器。

- 如果计数器超过链表的大小，则可能存在循环。

3. 复杂度：O(n)

注意：计数器与链表大小的比较，以及链表大小的更新操作必须是线程安全的。

下面是一段用于检测链表是否有循环的示例代码：

bool hasCycle(ListNode* head) {

ListNode* slow = head;

ListNode* fast = head;

while (fast != nullptr && fast->next != nullptr) {

slow = slow->next;

fast = fast->next->next;

if (slow == fast) {

return true;

}

}

return false;

}

以上是解决检测链表是否有循环问题的最佳算法及其原因。通过保持链表的大小并使用双指针方法，我们可以高效地检测出链表中是否存在循环。这种方法的时间复杂度为O(n)，并且在计数器与链表大小比较以及链表大小更新操作上保证了线程安全。

0