翻译自 链接



Floyd算法
这个问题可以使用两个指针来解决，一个快指针，一个慢指针。开始时这两个指针都指向链表头部。慢指针每次向下移动一个节点，快指针每次向下移动两个节点。如果链表中存在循环，快指针和慢指针就会相遇。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct node
{
    int data;
    struct node* next;
};
void detectLoop(struct node *head)
{
    struct node *slowPtr,*fastPtr;
    slowPtr = head;
    fastPtr = head;

    while(slowPtr!=NULL && fastPtr!=NULL && fastPtr->next!=NULL)
    {
        slowPtr = slowPtr->next;
        fastPtr = fastPtr->next->next;
        if (slowPtr == fastPtr)
        {
            printf("%s","Loop Detected");
            exit(0);
        }
    }
}

时间复杂度：O(n) 空间复杂度：O(1)