一起刷leetcode(141) : 判断链表是否有环


问题编号:141
问题描述:给你一个链表,请判断它是否有环。
PS:你能够在不使用额外存储空间的情况下解决这个问题吗?

欢迎把刷leetcode题的代码发上来,一起刷leetcode!
已邀请:

beta

赞同来自: July ictcxq 邹博 与我同行


思路:弄两个指针,一个(fast)跑的快, 一个跑(show)的慢,如果两者相遇则有环。

C++实现(已AC),时间复杂度O(n),空间复杂度O(1)
        class Solution {
        public:
            bool hasCycle(ListNode *head) {
                ListNode *slow=head,*fast=head;
                while(slow&&fast&&fast->next){
                    slow=slow->next;  //跑的慢
                    fast=fast->next->next;  //跑的快
                    if(slow==fast) return true; //相遇则有环
                }
                return false;
            }
        };

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~