LeetCode141之Linked List Cycle java題解

題目：

Given a linked list, determine if it has a cycle in it.

Follow up:

Can you solve it without using extra space?

之前我的一個同學在面試騰訊的時候問到一個問題：如何判斷一個連結清單存在環？當時我同學說了兩種思路：一，記錄從表頭開始周遊的節點，如果遇到已經存在的節點說明存在環；二，設定一個快一個慢的指針（即一個一次走一步，一個一次走兩步）如果他們能夠相遇就說明有環。

看到Leetcode這題判斷是否有環的時候，題目要求不能使用額外的空間，是以沒法使用第一種思路。相對來說，一快一慢這種解法更有通用性。下面就是就是這種解法的代碼。

public static boolean hasCycle(ListNode head) {
		if(head==null||head.next==null)//0個或1個結點肯定不能構成環
			return false;
		ListNode slow=head;
		ListNode fast=head;
		while(fast!=null&&fast.next!=null)
		{
			slow=slow.next;
			fast=fast.next.next;
			if(slow==fast)
				return true;	
		}
		return false;
        
    }           

做完這題有兩個值得注意的地方，一是0個或1個節點不能構成環，二，如果要使用某個節點的下下個節點（fast=fast.next.next)必須確定fast.next是存在的否在會報錯