44

有谁知道一种算法来查找链表是否在自身上循环，只使用两个变量来遍历列表。假设您有一个对象的链接列表，那么什么类型的对象都没有关系。我在一个变量中有一个指向链表头部的指针，我只得到另一个变量来遍历列表。

所以我的计划是比较指针值，看看是否有相同的指针。该列表的大小有限，但可能很大。我可以将两个变量都设置为头部，然后用另一个变量遍历列表，总是检查它是否等于另一个变量，但是，如果我确实遇到了一个循环，我将永远无法摆脱它。我认为这与遍历列表和比较指针值的不同速率有关。有什么想法吗？

4

7 回答 7

47

我建议使用Floyd's Cycle-Finding Algorithm aka The Tortoise and the Hare Algorithm. 它具有 O(n) 复杂性，我认为它符合您的要求。

示例代码：

function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

有关 Wikipedia 的更多信息：Floyd 的循环查找算法。

于 2009-01-30T08:01:32.840 回答
17

您可以使用海龟和兔子算法。

维基百科也有解释，他们称之为“弗洛伊德的循环寻找算法”或“龟兔赛跑”

于 2009-01-30T07:55:17.440 回答
9

绝对地。一种解决方案确实可以使用两个指针遍历列表，其中一个指针的移动速度是另一个指针的两倍。

从指向列表中任何位置的“慢”和“快”指针开始。运行遍历循环。如果“快”指针在任何时候都与慢指针重合，则您有一个循环链表。

int *head = list.GetHead();
if (head != null) {
    int *fastPtr = head;
    int *slowPtr = head;

    bool isCircular = true;

    do 
    {
        if (fastPtr->Next == null || fastPtr->Next->Next == null) //List end found
        {
            isCircular = false;
            break;
        }

        fastPtr = fastPtr->Next->Next;
        slowPtr = slowPtr->Next;
    } while (fastPtr != slowPtr);

    //Do whatever you want with the 'isCircular' flag here
}
于 2009-01-30T07:55:59.280 回答
3

我试图自己解决这个问题，并找到了一个不同的（效率较低但仍然是最佳的）解决方案。

这个想法是基于在线性时间内反转一个单链表。这可以通过在迭代列表的每个步骤中进行两次交换来完成。如果 q 是前一个元素（最初为 null）而 p 是当前元素，则 swap(q,p->next) swap(p,q) 将反转链接并同时推进两个指针。可以使用 XOR 来完成交换，以防止不得不使用第三个内存位置。

如果列表有一个循环，那么在迭代过程中的某一时刻，您将到达一个指针已更改的节点。你不知道是哪个节点，但是通过继续迭代，交换一些元素两次，你再次到达列表的头部。

通过两次反转列表，列表的结果保持不变，您可以根据您是否到达列表的原始头部来判断它是否有一个循环。

于 2009-05-05T17:52:17.520 回答
2 
int isListCircular(ListNode* head){
    if(head==NULL)
        return 0;
    ListNode *fast=head, *slow=head;
    while(fast && fast->next){
        if(fast->next->next==slow)
            return 1;
        fast=fast->next->next;
        slow=slow->next;
    }
    return 0;
}
于 2012-05-09T20:21:18.940 回答
1 
boolean findCircular(Node *head)
{
    Node *slower, * faster;
    slower = head;
    faster = head->next;
    while(true) {
        if ( !faster || !faster->next)
            return false;
        else if (faster == slower || faster->next == slower)
            return true;
        else
            faster = faster->next->next;
    }
}
于 2015-09-03T14:59:34.923 回答
0

将这个问题带到下一步将是识别循环（也就是说，不仅循环存在，而且它在列表中的确切位置）。Tortoise 和 Hare 算法可以用于相同的操作，但是，我们需要始终跟踪列表的头部。可以在此处找到该算法的说明。

于 2014-01-11T20:15:06.650 回答