环形链表

环形链表

给定一个链表,判断链表中是否有环。

进阶:
你能否不使用额外空间解决此题?

解法:

使用快慢指针,慢指针一次走一步,快指针一次两步,如果快指针和慢指针相遇则链表有环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class  {
public boolean hasCycle(ListNode head) {
if (head==null){
return false;
}
ListNode fast=head;
ListNode slow=head;
while (fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if (fast==slow){
return true;
}
}
return false;
}
}