Jessie-Cheng1 / xuexi

0 stars 0 forks source link

判断单链表是否有环 如何找到环的入口 #92

Open Jessie-Cheng1 opened 2 years ago

Jessie-Cheng1 commented 2 years ago
  1. 哈希表缓存 结点和出现的次数 每次遍历 都看哈希表中有没有出现过这个结点 有则出现了环
  2. 快慢指针法 两个指针指向这个链表的头节点。然后开始一个大循环,在循环体中,让指针low每次向下移动一个节点,让指针fast每次向下移动两个节点,然后比较两个指针指向的节点是否相同。如果相同,则判断出链表有环,如果不同,则继续下一次循环。
    bool IsExitsLoop(slist *head)
    {
    if(head == NULL)
        return false;
    slist *slow = head, *fast = head;
    while ( fast != NULL && fast->next !=NULL )
    {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast )
            return true;
    }
    return false;
    }

    找到环入口: image

数据结构之判断单链表有环和环的入口点 【算法】如何判断链表有环 判断单链表是否存在环