美文网首页
判断给定的链表中是否有环。如果有环则返回true,否则返回fal

判断给定的链表中是否有环。如果有环则返回true,否则返回fal

作者: 历十九喵喵喵 | 来源:发表于2020-12-18 18:53 被阅读0次

题目(牛客网):判断给定的链表中是否有环。如果有环则返回true,否则返回false。

你能给出空间复杂度

的解法么?

思路:定义两个指针,一个快指针,一个慢指针。快指针一次走两步,慢指针一次走一步,如果有环,那么总会有快指针等于慢指针的时候。

注意,要判断 快指针是否存在 空指针异常。

代码:

/**

* Definition for singly-linked list.

* class ListNode {

*    int val;

*    ListNode next;

*    ListNode(int x) {

*        val = x;

*        next = null;

*    }

* }

*/

public class Solution {

    public boolean hasCycle(ListNode head) {

        if(head==null){

            return false;

        }

        ListNode p=head;

        ListNode q=head;

        while(p!=null&&p.next!=null){

            p=p.next.next;

            q=q.next;

            if(p==q){

                return true;

            }

        }

        return false;

    }

}

相关文章

网友评论

      本文标题:判断给定的链表中是否有环。如果有环则返回true,否则返回fal

      本文链接:https://www.haomeiwen.com/subject/objfnktx.html