题目(牛客网):判断给定的链表中是否有环。如果有环则返回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;
}
}
网友评论