[数据结构]链表OJ--环形链表判断是否有环(快慢指针法)

141. ���形链表 - 力扣（LeetCode）

这里我采用的是快慢指针法,这是我认为最容易理解的方法,这个方法的思路是这样的.

我们可以定义两个指针一个快一个慢,如果这个链表有环,则快慢指针一定会相遇.

这里我画图举个例子:

我们很明显的可以看出,有环链表,快指针和慢指针存在相遇.

快指针跑得快，慢指针跑得慢。当慢指针和快指针从链表上的同一个节点开始移动时，如果该链表中没有环，那么快指针将一直处于慢指针的前方；如果该链表中有环，那么快指针会先于慢指针进入环，并且一直在环内移动。等到慢指针进入环时，由于快指针的速度快，它一定会在某个时刻与慢指针相遇，即套了慢指针若干圈。

接下来就让我们的想法实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    
}

它默认给我们创建了一个链表,给了这个链表的表头的地址

我们想可以考虑给的链表为空的情况,而且我们观察例子,我们可以看出存在只有一个头的没有下一个节点的链表,所以我门要对这两种情况进行判断

if(head==NULL||head->next==NULL)
{
    return false;
}

然后我们创建快慢指针:

struct ListNode* slow = head;
struct ListNode* fast = head;

然后我们让指针跑起来如果最后有一个指针跑到NULL说明,这个链表没有环,如果快慢指针不相等就接着跑,知道两个指针相遇.说明有环

  do
    {
        if (fast == NULL || fast->next == NULL)
         {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }while (slow != fast);
    return true;

最后组合起来

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return false;
    }
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    do
    {
        if (fast == NULL || fast->next == NULL)
         {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }while (slow != fast);
    return true;
}