給定一個鏈表锯茄，判斷鏈表中是否有環(huán)蜕便。
分析
由于每一個父親只有可能有一個孩子上真，故這里的環(huán)實(shí)際上是指list中某一個節(jié)點(diǎn)的孩子同時也是它自己或者他的祖先劳秋。 這個問題需要注意幾種情況：
- 空鏈表不成環(huán)
- 一個節(jié)點(diǎn)自環(huán)
- 一條鏈表完整成環(huán)
不能開額外的空間悦穿，即空間復(fù)雜度是o(1)攻礼。該問題是經(jīng)典面試問題，其標(biāo)準(zhǔn)解法是用兩個指針栗柒，一快一慢礁扮，如果在快的指針能夠追上慢的指針，則有環(huán)瞬沦，否則無環(huán)太伊。
代碼如下：
/**
* 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) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow)
return true;
}
return false;
}
}
