链表系列重新回归~
同时也深觉需要时刻关注对边界条件的处理~
之前就关注到链表判环这个问题,也知道是用快慢指针进行解决的,但是也就自己想了想,今天就借等待面华为的时候写一写~
关于思路
- 空链表、只有一个元素或者只有两个元素的链表不可能有环。
if(!head||!(head->next)||!(head->next->next)) return false;
- 加入只有三个元素并且恰巧有环,也可以直接排除
ListNode *slow = head;
ListNode *fast = head->next->next;
if(slow == fast) return true;
- 如果一个链表中包含环,那么从头节点出发的指针一直一直后移,绝对不会出现指针为空的情况。那么,也就是说,如果该指针为空,链表无环。因为慢指针遍历的节点总是快指针遍历过的,因此我们只判断快指针是否为空即可。
while(slow!=fast){
slow=slow->next;
// fast = fast->next->next;
if(fast->next&&(fast->next->next)) fast= fast->next->next;
else return false;
如果上述循环条件不满足,说明快慢指针相遇,即链表有环。
完整代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(!head||!(head->next)||!(head->next->next)) return false;
ListNode *slow = head;
ListNode *fast = head->next->next;
if(slow == fast) return true;
else{
while(slow!=fast){
slow=slow->next;
// fast = fast->next->next;
if(fast->next&&(fast->next->next)) fast= fast->next->next;
else return false;
}
return true;
}
}
};
关于快慢指针相遇问题
为什么有环就一定会相遇呢?这是一个物理问题,除了相遇,别无他法。