[数据结构]链表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;}