单向链表判断是否有环
2018-08-24 11:55:18 小德 算法 访问次数 570

image.png


这个问题可以使用两个指针来解决,一个快指针,一个慢指针。开始时这两个指针都指向链表头部。慢指针每次向下移动一个节点,快指针每次向下移动两个节点。如果链表中存在循环,快指针和慢指针就会相遇。时间复杂度:O(n) ;空间复杂度:O(1)

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

参考:https://blog.csdn.net/iccav/article/details/11682089