題目描述
給定一個(gè)鏈表，判斷鏈表中是否有環(huán)困乒。
為了表示給定鏈表中的環(huán)寂屏，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1娜搂，則在該鏈表中沒有環(huán)迁霎。
相關(guān)話題：?鏈表、雙指針????難度：?簡(jiǎn)單
示例 1：
示例 2：
示例 3：
進(jìn)階：
你能用 O(1)（即百宇，常量）內(nèi)存解決此問題嗎考廉？
思路：利用雙指針遍歷鏈表。
- 兩個(gè)指針携御，一個(gè)慢指針
slow昌粤，每次走一步；一個(gè)快指針fast啄刹，一次走兩步涮坐。 - 如果鏈表有環(huán)，
slow和fast會(huì)陷入死循環(huán)誓军，由于fast和slow的速度不同膊升，必定有一個(gè)時(shí)刻slow == fast；如果鏈表無環(huán)谭企，則fast指針會(huì)率先到達(dá)尾部廓译，結(jié)束评肆。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/*快慢指針，快一次兩步非区，慢一次一步瓜挽，如果最后重合就是有環(huán)*/
public boolean hasCycle(ListNode head) {
if(head == null)
return false;
ListNode slow = head;
ListNode fast = head;
while(fast.next != null&&fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
}
