目录
1.原题链接:
2.双指针:
我们可以定义两个指针,一个一次走一步,一个一次走两步,如果两个指针最后相遇了,那么,就说明这个链表有环。当快指针指向NULL或者快指针的next指向NULL时,说明链表没有环。
代码实现:
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
ListNode* slow=head;
ListNode* fast=head;
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
return true;
}
return false;
}
这时,你小小的脑袋里一定会有一个大大的疑惑吧。啊,为什么会这样?为什么慢指针走一步,快指针走两步,它们就会相遇?为什么不是慢指针走一步,快指针走三步、四步呢?
可莉不知道哦!
怎么可能嘛,这里我就浅浅的讲解一下,希望屏幕前的小姐姐、小哥哥们能够理解。^_^
证明:
这也许就是,只要我努力一点,我和她就还是会相遇的吧。
我们从这里可以看出,只要慢指针走一步,快指针走两步,如果链表有环,它们就必定相遇。
如果fast一次走3步,设最开始fast->slow之间的距离为x,则它们的距离会逐渐变为:
x
x-2
x-4
…
可以看出,x如果为偶数,两个指针会相遇;如果x为奇数,fast就会跳过slow,在极端情况下,如果它们之间的距离还是奇数,则会陷入死循环,永远不会相遇。同样的,可以证得快指针走3步、4步等的情况。
所以,如果我们走的太快,可能我们就永远都遇不到 ta ,也就永远都见不到了哦,可是如果我们回回头,可能 ta 就在我们身后哦(这里不能回头哦)。O.o
3.提交结果:
4.读书分享:
《道德经·第四十六章》:
天下有道,却走马以粪。天下无道,戎马生于郊。
祸莫大于不知足,咎莫大于欲得。
故知足之足,常足矣。
解释:
君王遵循“道”来治理天下,便让战马去耕种粪田。君王不遵循“道”来治理天下,战马只能在战场上生子。
最大的祸害莫过于不知足,最大的灾难莫过于贪得无厌。
所以只有知道满足而满足,才会永远的富足。