題目

給你一個鏈表的頭節(jié)點?head?，判斷鏈表中是否有環(huán)。

如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤?next?指針再次到達，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù)?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos?不作為參數(shù)進行傳遞?。僅僅是為了標識鏈表的實際情況。

如果鏈表中存在環(huán)?，則返回?true?。 否則，返回?false?。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。

示例?2：

輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。

示例 3：

輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環(huán)。

提示：

• 鏈表中節(jié)點的數(shù)目范圍是?[0, 104]
• -105 <= Node.val <= 105
• pos?為?-1?或者鏈表中的一個?有效索引?。

解答

源代碼

/*** 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;}
}

總結(jié)

這里使用雙指針學(xué)習(xí)一種新思路——快慢指針，快指針每次移動兩個節(jié)點，慢指針每次移動一個節(jié)點，若鏈表中存在環(huán)形，那么就像跑道上的追及問題，快慢指針一定會相遇。

在進行條件判斷和指針移動時要注意包含各種特殊情況，比如只有一個節(jié)點時，避免空指針問題。